BOJ 1398 - 동전 문제

문제

1원, 10원, 25원 동전으로 금액 N을 만들 때 필요한 최소 동전 수를 구하라.

입력

테스트 케이스 수와 각 금액 N이 주어진다 (최대 10^15).

출력

각 금액에 대해 최소 동전 수를 출력한다.

예제

입력	출력
`1` `93`	`5`

풀이

100 단위로 분할하여 DP로 해결한다.

0~99까지의 최소 동전 수를 1원, 10원, 25원 DP로 미리 계산한다
금액 N을 100으로 나누어 각 자릿수 그룹(2자리씩)의 최소 동전 수를 합산한다
100원 = 1원 x 100이므로 각 그룹은 독립적으로 계산 가능하다

핵심 아이디어: 동전 단위가 1, 10, 25이고 100 = 10^2이므로, 2자리씩 분리하면 0~99 범위의 DP만으로 큰 수도 처리 가능하다.

코드

import sys
input = sys.stdin.readline
 
dp = [0] * 101
for i in range(1, 101):
    dp[i] = dp[i - 1] + 1
    if i >= 10:
        dp[i] = min(dp[i], dp[i - 10] + 1)
 
    if i >= 25:
        dp[i] = min(dp[i], dp[i - 25] + 1)
 
for _ in range(int(input())):
    n = int(input())
    result = 0
    while n:
        result += dp[n % 100]
        n //= 100
 
    print(result)

복잡도

시간: O(N²)
공간: O(N)

문제