1107번 리모컨 백준

문제:www.acmicpc.net/problem/1107

1107번: 리모컨

이 문제를 처음에 봤을 때 lower_bound 와 upper_bound의 관계를 이용하면 되지 않을까 하고 이에 대하여 코딩을 짰었는데 100과 가까운 숫자에 대하여 어떻게 처리해야 할지 감이 안왔다. 

 

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(input())
m = int(input())
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)

참고:https://suri78.tistory.com/150

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

우선 if문은 사용 가능한 버튼을 저장하는 possible을 설정하였고 else문을 통해 고장나지 않았을 때에는 찾고자 하는 숫자에서 100을 뺀 값과 순전히 버튼을 눌렀을 때의 크기를 비교한다. 그리고 solve 함수를 통해 결과를 낸다.

solve함수를 해석하자면 우선 버튼을 누를 수 있는 숫자에 대하여 최대길이까지 브루트 포스 알고리즘을 적용한다.

ans = min( ans, len(str(int(now))) + abs(n-int(now)) )은 숫자길이 + ( + 또는 - 의 누르는 갯수)를 의미한다.

 

 

5457
3
6 7 8