[Python] 백준 1107번: 리모컨

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

1107번: 리모컨

 

import sys
input = sys.stdin.readline


def dfs(count):
    global minButtonClickCount, selectedDigits

    if (len(str(N))-1 <= count <= len(str(N))+1) and selectedDigits != []:
        targetChannel = convertDigitsToNumber(selectedDigits)
        channelDiff = abs(targetChannel-N)

        minButtonClickCount = min(
            minButtonClickCount, channelDiff+len(str(targetChannel)))

    if count == len(str(N))+1:
        return

    for i in range(10):
        if isAvailableDigit[i]:
            selectedDigits.append(i)
            dfs(count+1)
            selectedDigits.pop()


def convertDigitsToNumber(digits):
    convertedNumber = 0

    j = 0
    for i in range(len(digits)-1, -1, -1):
        convertedNumber += digits[i]*10**j
        j += 1

    return convertedNumber


isAvailableDigit = [True]*10

N = int(input())
M = int(input())
if M >= 1:
    for i in list(map(int, input().split())):
        isAvailableDigit[i] = False

# +-만으로 이동
minButtonClickCount = abs(N-100)

if M <= 9:
    # 가장 가까운 채널 입력 -> +- 입력
    selectedDigits = []
    dfs(0)

print(minButtonClickCount)

 

우선 +-만 이용했을 때의 minButtonClickCount를 먼저 대입해준다.

이후에 dfs+백트래킹을 돌아주는데, selectedDigits를, 고장나지 않은 숫자 내의 범위 내에서 추가시킨다. 그리고 dfs의 count 인자가 (N의 길이-1) ~ (N의 길이+1)일 때, minButtonClickCount를 갱신시켜준다.

여기서, 범위가 저렇게 되는 이유는 예시를 들면서 설명하겠다.

우선, N의 길이-1을 고려하는 것은, 가령 채널 10에 도달해야하는데 0, 1이 고장났다고 하자, 그러면 채널 9에 가서 +를 1번 누르면 되는데 이 때 9는 10보다 길이가 1이 낮다.

그리고 N의 길이+1을 고려하는 건, 채널 99에 도달해야하며 9가 고장났다고 했을 때 채널 100으로 가서 -를 해주면 되기 때문이다.