[백준] 1107 - 리모컨

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

1107번: 리모컨

문제 한줄 이해

-리모콘의 숫자가 망가져 있을 수도 있고 아닐 수도 있는 상황에서 N채널로 가기위한 최소 버튼 입력 수 구하기

생각난 풀이

1번째 방법: 백트래킹을 통해 N채널 자릿수와 자릿수 +1, 자릿수 -1 의 경우의 수를 담아 값을 갱신했다.

자리수 -1 과 자릿수 +1 을 해주는 이유는 간단한 예를 들면 999 채널로 가려고 할때 망가진 숫자가 9가 망가졌다고 치자. 

그럼 경우의 수중 111,112...888까지 갈것이고 이때 8을 3번 누르고 111번의 +를 해줘야한다.

하지만 1000으로 만들면 1한번 0 3번 누르고 한번 -를 해주면 5번이면 충분하기때문이다.

import sys
numlist = [0,1,2,3,4,5,6,7,8,9]
N = sys.stdin.readline().strip()
M = int(sys.stdin.readline())

# 망가진게 있는 경우에만 받아오기
if M > 0:
    broke = list(map(int, sys.stdin.readline().split()))
    for i in broke:
        numlist.remove(i)
        
# 현재 채널에서 + - 만해서 저장
result = abs(100-int(N))

def dfs():
    # 백트래킹을 통해 모든 경우의 수 계산
    global result
    if len(sublist) >0:
        if len(sublist) == len(N)-1 or len(sublist) == len(N) or len(sublist) == len(N)+1:
            nown = int(''.join(map(str,sublist)))
            if abs(nown-int(N)) + len(sublist) < result:
                result = abs(nown-int(N)) + len(sublist)
            if len(sublist) == len(N)+1:
                return
    for i in range(len(numlist)):
        sublist.append(numlist[i])
        dfs()
        sublist.pop()
        
sublist = []
if numlist:
    dfs()
print(result)