CSES 3. Removing Digits (1637)

출처: https://cses.fi/problemset/task/1637

---

문제 설명

You are given an integer n. On each step, you may subtract from it any one-digit number that appears in it.

How many steps are required to make the number equal to 0?

입력 

The only input line has an integer n.

출력

Print one integer: the minimum number of steps.

입력 예

27

출력 예

5

Explanation: An optimal solution is  27 , 20(-7), 18(-2), 10(-8), 9(-1) - 0 (-9)

제약조건

• 1 <= n <= 10^6

---

문제 풀이

어떤 수의 자리수 중에서 가장 큰 숫자를 찾아서, 그 숫자들을 계속 빼주는 방법이다. 

최적의 경우의 수는 각 자리의 수를 빼서 나온 수의 경우의 수 +1 중에서 가장 작은 것이 된다. 

 

입력 N 의 크기를 생각해보면, 기록할 필요 없이 가장 큰 자리수를 찾아서 빼내고, 다시 재귀적으로 돌려도 충분할 것 같다.

프로그램 내용

...
    vector<int> DP(nNum+1, 1e9);

    DP[0] = 0;
    for (int idx=1; idx <= nNum; ++idx)
        int tmp = idx;
        while(tmp)
            int r_digit = tmp % 10;
            DP[idx] = min( DP[idx], DP[idx-r_digit] + 1);
            tmp /= 10;
...

 

Dynamic Programming ( link )