숫자 빼기로 0 만들기

문제

각 단계마다 현재 숫자에 포함된 0이 아닌 십진수 한 자리를 선택하여 그 숫자를 뺍니다. 매 단계 후에는 새로운 값에서 자릿수를 선택합니다. 0에 도달하기 위해 필요한 최소 단계 수를 구하세요.

removing_digits(n)을 구현하세요.

n: 양의 시작 숫자입니다.

가장 적은 빼기 단계 수를 반환하세요.

1 ≤ n ≤ 1,000,000. 0을 빼는 것은 유효한 동작이 아니므로 제외됩니다.

예시 1

입력:
n = 14

예상 출력:
expected = 3

입력:
long long n = 14;

예상 출력:
long long expected = 3;

입력:
long n = 14;

예상 출력:
long expected = 3;

14 → 10 → 9 → 0은 세 단계가 필요합니다. 어떤 첫 번째 빼기 선택도 두 단계 만에 0에 도달할 수 없습니다.

예시 2

입력:
n = 7

예상 출력:
expected = 1

입력:
long long n = 7;

예상 출력:
long long expected = 1;

입력:
long n = 7;

예상 출력:
long expected = 1;

유일한 자릿수 7을 빼면 바로 0이 됩니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

각 수는 한 자리 숫자를 빼서 도달할 수 있는 더 작은 수들의 최적 답에 의존한다.

힌트 2

n까지의 모든 값에 대해 동적 계획법을 쓰면 중복 계산을 피할 수 있다.

힌트 3

뺄 수 있는 숫자는 매번 달라지고, 0은 절대 유효한 선택이 아니다.

예상 복잡도

시간 O(n * d), 추가 공간 O(n)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.