[BOJ/백준] 1398 동전

import sys

def input():
    return sys.stdin.readline().rstrip()

T = int(input())
dp = [i for i in range(101)]

for i in range(100):
    for coin in [10,25]:
        if i +coin > 100:continue
        dp[i+coin] = min(dp[i+coin],dp[i]+1)
for _ in range(T):
    N = int(input())

    answer = 0
    while N>0:
        answer += dp[N%100]
        N//=100
    print(answer)

 

 

이 문제는 100까지의 최소 코인의 개수를 구해준 뒤에, 100단위로 나눠주면서 그 개수를 더해주면 된다.

 

왜냐하면

 

이 문제에서 쓰이는 동전은 [1,10,25]로 되어있고

 

각 100^k 만 곱해진 동전이기 때문이다.