[python] 백준 1398 동전 문제

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

1398번: 동전 문제

 

 

문제 해결

• 동전이 1, 10, 25... 패틴을 확인 할 수 있는지 문제이다.
• 동전의 수열 집합을 A라 할 때 $A_{i}$ = 100$A_{i-3}$ 임을 확인 할 수 있으면 문제는 쉬워진다.
• 100 단위로 동전을 최대한 적은 수로 처리하는 방법을 생각하면 된다.

CODE

t = int(input())
coins = [1, 10, 25] # 이 형태로 계속 간다.
for _ in range(t):
    x = int(input())
    answer = 0
    dp = [10**15 for _ in range(100)] # 최댓값
    dp[0] = 0
    for c in coins:
        for i in range(c,100):
            dp[i] = min(dp[i], dp[i-c]+1)
    while x:
        answer += dp[x%100] #100단위씩 확인했을 때
        x //= 100
    print(answer)