모든 챌린지
보통 1명 해결 정답률 100.0%

Subtract Digits to Reach Zero

Use as few digit subtractions as possible to reach zero.

배우게 될 내용

  • Model a process as states and moves
  • Compute the minimum steps to zero
  • Compare DP with a greedy shortcut

문제

번역본 보기

At each step, choose a nonzero decimal digit currently present in the number and subtract that digit. Digits are taken from the new value after every step. Find the minimum number of steps needed to reach zero.

Implement removing_digits(n).

Input

n: The positive starting number.

Output

Return the fewest subtraction steps.

제약 조건

1 ≤ n ≤ 1,000,000. Subtracting zero is not a useful move and is excluded.

예시

예시 1
입력:
n = 14

예상 출력:
expected = 3
입력:
long long n = 14;

예상 출력:
long long expected = 3;
입력:
long n = 14;

예상 출력:
long expected = 3;

설명

14 → 10 → 9 → 0 uses three steps. Neither possible first subtraction can reach zero in only two steps.

예시 2
입력:
n = 7

예상 출력:
expected = 1
입력:
long long n = 7;

예상 출력:
long long expected = 1;
입력:
long n = 7;

예상 출력:
long expected = 1;

설명

Subtract the only digit, 7, to reach 0 immediately.

접근 방법

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

힌트 1

Each number depends on the best answer for smaller numbers reachable by subtracting one digit.

힌트 2

Dynamic programming over all values up to n avoids repeated work.

힌트 3

Remember that the available digits change after every subtraction, and zero is never a valid choice.

예상 복잡도

O(n * d) time, O(n) extra space

참고 자료

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

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 942 ms - 2/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.