Removing Digits

https://cses.fi/problemset/result/3889109/

https://cses.fi/problemset/result/3889109/

이 문제는 주어진 숫자 n이 가진 각 자리의 수 중에서 하나씩 빼어서 0이 되는 최소의 연산 수를 구하는 것이다. 즉, 최적해는 27→20→18→10→9→0.으로 총 5번의 연산이 최소한 필요하다. 여기서 dp[x]를 x라는 수를 0으로 만들기 위한 최소의 연산 수라고 정의하자.

우선, 27의 자리의 수는 2, 7이다. 그러므로 dp[27]을 구하려면, dp[25], dp[20] 으로 가는 2가지 경우가 있다. 그리디로 풀자면 dp[20]으로 무조건 가면 되지만, dp로 풀자면 두 경우를 모두 계산해서 비교해봐야 한다. 단, 주의할 것은, 각 상태 사이의 관계식이다. 각 자리 수를 d라 할 때, 모든 자리의 수 d에 대해 loop을 돌려 최소의 대안을 찾기 위해, 직전 loop 에서 연산된 내용인 dp[x] (첫 loop이었다면, 초기값인 INF) 와 지금 loop에서의 대안을 비교한다.

dp[x] = min(dp[x], dp[x - d] + 1)

이 된다. dp[20]에서 dp[27]로 올 때 연산 수가 1번 더해져야 하기 때문이다.

코드는 다음과 같다.

n = int(input())

dp = [0] + [float('inf')] * n
for x in range(1, n + 1):
    num, digits = x, []
    while num:
        digits.append(num % 10)
        num //= 10
    for d in digits:
        if x - d >= 0:
            dp[x] = min(dp[x], dp[x - d] + 1)

print(dp[n])