이번 문제는 그리디와 DP를 이용하여 해결하였다. 처음에는 주어진 수에 대하여 가능한 동전을 모두 리스트에 담고, 이 리스트를 내림차순으로 순회하며 주어진 금액에 그때그때 가능한 많은 동전을 사용하여 금액이 0이 될때가지 반복하도록 하였다. 테스트케이스는 잘 맞았지만, 33%에서 오답처리를 당했다. 다른 방법이 도저히 생각나지 않아 다른 사람의 풀이를 참고하였다.

다른 사람들 모두 DP를 함께 사용하여 풀이하였다. 동전의 패턴을 보면 1, 10, 25에 100을 계속해서 곱한 수들로 이뤄져 있기 때문에 동전 리스트에는 1, 10, 25만 들어갔다. 그리고 길이가 100인 dp리스트를 최댓값으로 채운다. dp[0]을 0으로 갱신해주고, 동전 리스트를 순회하며 동전부터 99까지의 반복문을 통해 dp[i]를 dp[i]와 dp[i-c]+1 중의 최솟값으로 갱신해준다. 그리고 결과 변수에 dp[cost%100]을 더해주고, 금액을 100으로 나눠준다. 이 과정을 cost가 0이 될때까지 반복한다.

Code

t = int(input())
for _ in range(t):
    cost = int(input())
    k = len(str(cost))
    coins = [1, 10, 25]
    answer = 0
    dp = [10**15+1 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 cost:
        answer += dp[cost%100]
        cost //= 100
    print(answer)