https://www.acmicpc.net/problem/1107
접근
- 최대로 버튼을 누른 횟수는 + 또는 - 버튼만 사용한 횟수이다.
- 숫자 버튼을 눌러 어떤 채널로 이동한 후 + 또는 - 버튼으로 이동하려는 채널에 도달할 수 있다.
- 채널은 무한대이기 때문에 탈출 조건이 없으면 무한 루프에 빠진다.
풀이
from sys import stdin
def check_button(limit, next):
move_cnt = res
channel = 100
while channel != limit:
for num in str(channel):
if num in broken: # (1)
break
else:
move_cnt = min(move_cnt, len(str(channel)) + abs(channel - n)) # (2)
channel += next
return move_cnt
n, m = int(stdin.readline()), int(stdin.readline())
broken = set(stdin.readline().split())
res = abs(n - 100) # (3)
if n == 100: # (4)
print(0)
elif m == 0: # (5)
print(min(res, len(str(n))))
elif m == 10: # (6)
print(res)
else:
if 100 < n:
print(min(res, check_button(999894, 1))) # (7)
else:
print(min(res, check_button(-1, -1)))
- (1) 고장난 숫자가 포함되어 있을 경우 탈출하여 최솟값을 갱신하지 않는다.
- (2) 고장난 숫자가 포함되어 있지 않을 경우 버튼 횟수의 최솟값을 갱신한다.
- (3) + 또는 - 버튼으로만 누른 횟수를 기준으로 한다.
- (4) 현재 채널과 같을 경우 0이다.
- (5) 고장난 버튼이 없을 경우 + 또는 -버튼만 누르거나 숫자 버튼만 누른 경우 중에서 최솟값이다.
- (6) 0에서 9까지 모든 버튼이 고장났을 경우 + 또는 -버튼만 사용한 횟수이다.
- (7) 채널은 무한이기 때문에 탈출 조건을 두어야 한다. 이동하려는 채널은 최대
500,000
채널이고, 최대로 버튼을 누른 횟수는100
채널에서 +버튼만 사용한 499,900이다.
반대로 채널 이동 후 -버튼으로500,000
채널에 도달할 수 있다. 숫자 버튼을 누른 횟수 6번 포함999,894
채널로 이동해서 499,894번 -버튼을 누르면 되지만, 최대 횟수인 499,900번보다 작아야 하기 때문에999,983
채널까지 반복한다.