[백준/BOJ] gold2 - 1398번 동전 문제 (Python)

▶1398 - 동전 문제

▶문제

구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다.

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000...

즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25 × 100K인 동전이 있는 것이다.

구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사 가려고 한다. 초콜릿의 가격이 주어졌을 때, 이를 구매하기 위해 필요한 동전 개수의 최솟값을 구해보자. 각 동전의 개수는 무한하고, 구매할 때는 정확하게 초콜릿의 가격만큼만 지불해야 한다.

 

▶입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.

 

▶출력

총 T개의 줄에 각각의 테스트 케이스의 필요한 동전의 개수를 출력한다.

 

▶예제

 

▶풀이

숫자가 커지면 필요한 동전의 단위도 커지게 된다.

그렇게 되면 k가 커지게 되고... 어디까지 k를 지정해야 할지 모른다.

 

그래서 고민해본 결과 1, 10, 25만 동전으로 두기로 했다.

이유는 100, 1000, 25000 / 10000, 100000, 2500000...

뒤로 더 가게 되면 100씩 곱해지게 된다.

 

dp는 0부터 99까지 설정해두고,

돈은 100으로 나눈 나머지로 보고 계산해서 answer에 더해주고,

돈은 //= 100을 해주면 된다.

 

글을 잘 쓰는 게 아니라서 글만 보면 이해가 안 갈 수 있다.

코드를 보면 바로 이해될 거다.

t = int(input())
coin = [1, 10, 25]
result = []
for i in range(t):
    c = int(input())
    dp = [10 ** 15 + 1 for _ in range(100)]
    dp[0] = 0

    for co in coin:
        for j in range(co, 100):
            dp[j] = min(dp[j], dp[j-co] + 1)

    answer = 0
    while True:
        answer += dp[c % 100]
        c //= 100
        if c == 0:
            result.append(answer)
            break

for re in result:
    print(re)