(Python) - BOJ(1107번) : 리모컨

https://www.acmicpc.net/problem/1107

1107번: 리모컨

---

• 해설 : 

수빈이는 리모컨을 조작하여 원하는 채널로 이동하고 싶다. 

그러나 리모컨의 버튼이 몇 개 고장나서 직접적으로 이동할 수 없는 상황이다.

고장나지 않은 버튼과 +, -버튼만을 이용하여 원하는 채널로 바꿀 때 버튼을 누르는 최소 횟수를 찾는 문제이다.

수빈이의 현재 채널은 100번이다.

 

 

 

---

• 풀이 :

우선 고장난 버튼을 제외하고 가능한 버튼에 대한 정보를 담아두고 이 정보를 이용해서 1부터 1,000,000까지 모든 값을 만들 수 있는 최소 횟수를 탐색한다. 찾으려는 채널의 최댓값이 500,000이지만 1,000,000까지 탐색하는 이유는 

100번에서 500,000을 가려고 +를 499,900번을 누르는 것 보다 555,555에서 -를 55,555번 누르는게 훨씬 빠르기 때문이다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    N = int(input())
    M = int(input())
    B = [str(i) for i in range(10)]
    b = list(input().split())
    b = list(set(B)-set(b))
    ans = abs(100-N)
    for num in range(1000001):
        num = str(num)
        for j in range(len(num)):
            if num[j] not in b:
                break
            elif j == len(num) - 1:
                ans = min(ans, abs(N - int(num)) + len(str(num)))
    print(ans)