https://www.acmicpc.net/problem/1107
풀이
이것저것 여러 방법을 생각해 봤으나, 마땅한 수가 생각나지 않았음.
문제 조건에서 채널이 500,000개 정도였기 때문에 Brute-Force로 시도해볼 만하다고 생각해서 Brute-Force로 실행.
다만 0~500,000 까지의 수를 모두 대입해 보기보다는, 고장난 버튼을 염두에 두고,
조합 가능한 모든 6자리까지의 경우의 수를 미리 만들어 두고, 그 이후 처리하는 것이 속도 면에서 이득이다.
# 100에서 움직일 때와 버튼을 누르고 움직일 때, 둘 중 최솟값을 채택 channels[ch] = min(abs(goal - 100), len(str(ch)) + abs(goal - ch))0 ~ 500,000 까지의 모든 수를 대입한다면, 위 과정을 500,000번 반복하게 됨,
그러나 버튼이 1개라도 고장난다면, 조합 가능한 6자리의 모든 경우의 수는 10^6 / 2 = 약 500,000개 정도가 되고,
2개 이상 고장난다면 1/2로 다시 전체 경우의 수가 줄어드므로, 모든 조합을 저장하는 과정이 있지만,
평균적인 속도 면에서 유리함을 알 수 있음.
다만 이 문제에서 주의해야 할 점은, 고장난 버튼의 개수가 0일 때 3번째 줄(고장난 버튼)의 입력을 받지 않도록 처리해 주어야 입출력 오류를 범하지 않을 수 있고,
모든 버튼이 고장난 경우에는 channels dictionary가 빈 dictionary가 되어, min() 함수에서 런타임 에러 (ValueError)를 일으키므로, 두 경우를 따로 처리해 줘야할 것.
import sys
input = sys.stdin.readline
current = 100
goal = int(input())
break_cnt = int(input())
button = [i for i in range(10)]
breakButton = []
if break_cnt != 0:
breakButton = list(map(int, input().split()))
button = list(set(button) - set(breakButton))
# 이동하려는 채널이 1~500,000이기 때문에 Brute Force로 접근해도 할만 함.
# 6자리 내에서 모든 만들 수 있는 수의 경우를 만들고, goal과의 수 차이를 측정.
channels = dict([])
# 1~6자리수의 가능한 모든 조합을 dictionary에 저장
for a in button:
channels[a] = 0
for b in button:
channels[int(str(a)+str(b))] = 0
for c in button:
channels[int(str(a)+str(b)+str(c))] = 0
for d in button:
channels[int(str(a)+str(b)+str(c)+str(d))] = 0
for e in button:
channels[int(str(a)+str(b)+str(c)+str(d)+str(e))] = 0
for f in button:
channels[int(str(a)+str(b)+str(c) +
str(d)+str(e)+str(f))] = 0
# 모든 채널에 대해
for ch in channels:
# 100에서 움직일 때와 버튼을 누르고 움직일 때, 둘 중 최솟값을 채택
channels[ch] = min(abs(goal - 100), len(str(ch)) + abs(goal - ch))
# 모든 버튼이 고장난 경우, ch.100 부터 +, - 버튼으로만 도달해야 하므로 처리.
if channels:
print(channels[min(channels, key=channels.get)])
else:
print(abs(goal - 100))