문제 설명

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

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

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

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

입력 조건

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

출력 조건

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

전체 코드

import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
if m > 0:
    broken = set(map(int, sys.stdin.readline().split()))
else:
    broken = set()

dp = [sys.maxsize] * 1000001
dp[100] = 0


# 최대 6자리이므로 O(1)에 해당하는 시간 복잡도
def get_count(num: int) -> int:
    cnt = 0

    while num > 0:

        if num % 10 in broken:
            return -1
        else:
            cnt += 1

        num //= 10

    return cnt


# ->로 가면서 i번째 숫자를 분해한다. 고장난 버튼에 없는 수로만 이루어져 있다면, 해당 수의 개수들로 세기. 시간 복잡도는 O(n)
for number in range(1, 1000001):
    count = get_count(number)

    if count != -1:
        dp[number] = min(dp[number], count)

# 0은 get_count()에 의해 계산이 안되므로 예외 처리.
dp[0] = 1 if 0 not in broken else dp[0]

# ->로 가면서 + 버튼을 눌렀을 때를 보자. 시간 복잡도는 O(n)
for i in range(1, 1000001):
    dp[i] = min(dp[i], dp[i - 1] + 1)

# <-로 가면서 - 버튼을 눌렀을 때를 보자. 시간 복잡도는 O(n)
for i in range(1000000, 0, -1):
    dp[i - 1] = min(dp[i - 1], dp[i] + 1)

# 총 시간 복잡도는 O(n) * 3 * 6 -> O(n)
print(dp[n])

해설

예를 들어, n=22, m=2, broken=[1,5]라고 하자.
sys.maxsize를 x라고 표기한다면, 첫번째 for 문에 의해 숫자를 분해하여 최솟값들을 구한다면 다음과 같다. (i,dp[i]) 형식으로 표기한다.

[(0,1),(1,x),(2,1),(3,1),(4,1),(5,x),(6,1),(7,1),(8,1),(9,1),(10,x),(11,x),(12,x),(13,x),(14,x),(15,x),(16,x),(17,x),(18,x),(19,x),(20,2),(21,x),(22,2),(23,2)...]

두 번째 반복문은 +를 한칸 해보는 것이다.
동일한 방식으로 표기하면, 다음과 같다.

[(0,1),(1,2),(2,1),(3,1),(4,1),(5,2),(6,1),(7,1),(8,1),(9,1),(10,2),(11,3),(12,4),(13,5),(14,6),(15,7),(16,8),(17,9),(18,10),(19,11),(20,2),(21,3),(22,2),(23,2)...]

세 번째 반복문은 <- 방향으로 -를 한칸 해보는 것이다.
[(0,1),(1,2),(2,1),(3,1),(4,1),(5,2),(6,1),(7,1),(8,1),(9,1),(10,2),(11,3),(12,4),(13,5),(14,6),(15,7),(16,6),(17,5),(18,4),(19,3),(20,2),(21,3),(22,2),(23,2)...]

16,17,18,19의 경우 20부터 시작해서 <-로 하는게 버튼을 덜 누름을 알 수 있다.

500000
8
0 2 3 4 6 7 8 9

위의 예제의 경우, 첫 번째 반복문에서 dp[511111]=6이 나온다.
->로 +하는 방향은 별로 중요하지 않다.
<-로 -하는 방향은 511111과 500000의 차이는 111111이므로 111111+6=111117이다.