링크

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

풀이

해당 체널에 가는 경우에 수는 3가지이다.

• 체널버튼을 눌러서 도달하는경우
• 작은 체널로 이동후 + 버튼을 눌러서이동
• 큰체널로 이동후 -버튼을 눌러이동

import sys
sys.setrecursionlimit(200000)
target = input()
dbn = int(input())
if dbn>0:
    dbtn = input().split()
else:
    dbtn = []

answer = abs(100-int(target))
tlist = list(target)
nodbtn = []
for btn in "0123456789":
    if btn not in dbtn:
        nodbtn.append(btn)

def BF(now,idx,cnt):
    global answer
		#버튼만 눌러서 이동 가능한 경우
    if now==target:
        answer = min(answer,cnt)
        return
		#같은 자리수에서 +,ㅡ로이동
    if len(now)==len(target):
        tnow = int(now)
        if tnow>int(target):
            if '-' not in dbtn:
                answer = min(answer,cnt+abs(tnow-int(target)))       
        else:
            if '+' not in dbtn:
                answer = min(answer, cnt+abs(tnow-int(target)))
    #한자리큰 수에서 -로이동
    if len(now)-1 == len(target):
        tnow = int(now)
        if '-' not in dbtn:
            answer = min(answer,cnt+abs(tnow-int(target)))
            return
        else:
            return
        return
    #한자리 작은 수에서 +로이동    
    if len(now)+1==len(target):
        if now!="":
            tnow = int(now)
            if '+' not in dbtn:
                answer = min(answer, cnt+abs(tnow-int(target)))
            else:
                return

    
        
   
    for btn in nodbtn:
        BF(now+btn,idx+1,cnt+1)

#print(nodbtn)
BF("",0,0)
#print("끝")
print(answer)