[Python] 백준 1398: 동전문제

https://www.acmicpc.net/problem/1398

1398번: 동전 문제

1. 10^K인 동전과 25*100^K 동전이 있는데 값은 10^15보다 작거나 같은 자연수이므로

  1, 10, 25, 100, 1000, 2500, 10000, 100000,...로 10^15 이하까지 반복된다

2. 근데 계속보면 1, 10, 25의 값에 100씩 곱해지는 동전이 반복되는 것을 알 수 있다. (1, 10, 25), (100, 1000, 2500),

(10000, 100000, 250000) ......

3. 그러므로 값을 2자리씩 끊어서 dp로 연산하면 최소의  값이 나온다.

T = int(input())
k = 0
coin = [1, 10, 25]

while T:
    T -= 1
    x = int(input())
    ans = 0
    dp = [10**15+1 for _ in range(100)]
    dp[0] = 0
    for c in coin:
        for i in range(c, 100):
            dp[i] = min(dp[i], dp[i-c]+1)
    while x:
        ans += dp[x % 100]
        x //= 100
    print(ans)