[백준 1107번] 리모컨

n = int(input())
m = int(input())
ans = abs(100 - n)

if m != 0: # 고장난게 있을 경우만 인풋을 받음
    broken = list(input().split())
else:
    broken = []

# 작은수에서 큰수로 이동할땐 500,000 까지만 보면 되지만
# 반대로 큰수에서 작은수로 내려올수도 있으므로 1,000,000 까지 봐야함
for i in range(1000001):
    for j in str(i):
        if j in broken: #해당 숫자 버튼이 고장난 경우 스탑
            break
    else: # 번호를 눌러서 만들 수 있는 경우엔
        ans = min(ans, len(str(i)) + abs(i - n)) #min(기존답, 숫자 버튼 클릭 수 + 해당 번호로부터 타겟까지의 차이)

print(ans)

이번 문제는 현재 채널이 100번이라는 가정하에 주어진 N 채널로 이동하기 위해서 버튼을 눌러야 하는 횟수의 최소값을 구하는 문제이다. 다만, '리모콘에서 고장난 숫자가 존재할 수 있다는 점'과, '채널은 무한대로 있다는 점'을 유의해서 풀어야 한다.

 

처음에 이 문제를 풀이할 때는 각 자리수에서 고장나지 않은 가장 가까운 수를 구하는 함수를 구현하고, 각 자리수마다 따로 카운팅하는 방식으로 진행했는데, 반례가 발생하고 몇시간째 제대로 풀리지않아 결국 다른 사람의 풀이를 참고하였다.

 

이 문제의 핵심은 '번호를 눌러서 만드는 경우'와 '번호를 별도로 누르지 않고 +/- 로만 이동해서 만드는 경우'를 비교하여 최소 값을 모든 경우를 탐색하면서 최적 값을 찾아내는 것이다.

 

번호를 눌러서 만드는 경우에는 먼저 고장난 숫자가 포함되면 안되기 때문에 for-else 문을 활용하여 고장난 숫자가 하나라도 있는 경우에는 Skip 하고, 만들 수 있는 경우에는 해당 숫자 버튼 클릭수(len(str(i)))와 해당 번호로부터 N을 만들기 위해 +/-를 눌러야 하는 횟수(abs(i-n))를 더해준다.

 

⭐️ for-else문 : else문은 for문이 break 없이 온전하게 완료되면 작동한다. 

 

이 값을 ans(초기 값은 100에서 +/-를 눌러서 만드는 경우)와 비교하여 최소 값을 모든 경우에 대하여 탐색하면서 갱신 시켜주다보면 최소값이 나오게 된다.

 

복잡하게 생각했던 문제였는데, BruteForce를 사용하니 간단하게 풀 수 있다는 것이 조금 허무했지만 for-else 문도 알게 되고 여러모로 도움이 많이 되었던 문제였다.