<백준 Python> 1107 리모컨 골드V

문제 문제링크
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

# 1107번 리모컨
n = int(input())# 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000) # 5457
m = int(input()) #  고장난 버튼의 개수 M (0 ≤ M ≤ 10)
broken = [False] * 10
if m>0:
    a = list(map(int, input().split())) # 6 7 8
else:
    a = []

for x in a :
    broken[x] = True

def possible(c): # 이동할수 있는 지 여부 보기 # c로 이동할 수 있으면 c에 숫자의 개수
    if c == 0:
        if broken[0] :
            return 0 # 최소
        else:
            return 1 # 고장난거면 1
    l = 0
    while c > 0: 
        if broken[c % 10]: # 고장난 버튼이 있으면 0 
            return 0
        l += 1   # 그게아니면 길이를 계속 1 추가 길이 4까지감
        c //= 10 # 5457=>545, 545=>54, 54=>5
    return l 

ans = abs(n-100) # 수빈이가 지금 보고 있는 채널은 100번이다. 일일이 +-로 이동하는 횟수
for i in range (0,1000000+1):
    c = i # 0부터 ㄱㄱ
    l = possible(c) # 100에서 c로 숫자버튼으로 이동, 횟수는 l에 들어잇음
    if l > 0: # 0이면 불가능하니까 0보다 크면 이동할수 있음 
        press = abs(c-n) # c=>n 이동 +- 버튼으로 숫자 차이 구하기
        if ans > l + press: # 실제로 버튼을 누른 횟수 길이 더하기 +-숫자차이
            ans = l + press
print(ans)