[백준알고리즘] 1107번: 리모컨 -Python

[백준알고리즘] 1107번: 리모컨 -Python

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

1107번: 리모컨

브루트 포스로 해결해야 하는 건지 모르고 이상하게 풀었었다... 조건을 다 맞추려고 하다 보니 오류가 계속 발생하고 통과가 안 되는 반례가 계속 존재했다.

 

이 문제의 경우에는 MAX가 500000으로 depth도 얕기 때문에 recursion depth도 6으로 낮고, 0~9까지의 각 자리 숫자가 다 가능하다고 했을 때도 경우의 수가 10^6으로 많지 않다.

 

보통 1초에 반복 횟수가 10^8 (1억)을 초과할 경우 시간 초과가 발생한다고 보기 때문에 충분히 여유있다.

https://book.algospot.com/estimation.html

 

따라서 가능한 번호의 버튼을 모두 누르면서 비교해 최소 클릭 횟수를 구하도록 해주었다.

 

import sys
 
def solve(sub):
    global ans
    for p in possible:
        now = sub + str(p)
        ans = min( ans, len(str(int(now))) + abs(n-int(now)) )
        if len(now) < 6:
            solve(now)
    
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
ans = abs(n-100)
 
possible = set()
if m:
    broken = set(map(int, sys.stdin.readline().split()))
    possible = set(i for i in range(10)).difference(broken)
else:
    ans = min(ans, len(str(n)))
 
solve('')
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다