[Python] [BOJ] 동전 문제(1398)

💡 문제 해결

1. 1, 10, 25의 동전으로 모든 경우의 동전이 생성 가능하므로 1, 10, 25를 포함한 리스트 생성
2. 100단위로 값이 중복되어 생성되므로 100크기의 dp리스트를 생성
3. 0부터 99원을 생산할때 필요한 최소 동전 개수를 구하며 dp리스트 갱신
4. 자동차 비용에 대한 값이 전부 지불되기까지 dp리스트에 저장된 값을 호출
5. 호출된 값을 answer에 더하며 반복문이 종료되면 answer을 출력

📌 1과 10을 통해 10^K, 25를 통해 25*100^K의 모든 동전 생성 가능
📌 위의 방법대로라면 1, 10, 25를 활용해 100, 1000, 2500의 동전이 생성 가능하고, 해당 동전들을 통해 구할 수 있는 값은 100^K마다 같은 값을 도출
📌 100^K마다 같은 값을 도출한다는 것은 반복된 주기를 가진다는 뜻
📌 dp리스트를 갱신하는 과정은 해당 금액을 만드는데 작은 동전부터 사용했을 때 만드는 순서이고, 동전이 커지면 해당 금액 동전을 사용하여 만들 수 있는 금액의 최소 동전개수로 나아감

🧾 문제 설명

김형택이 세운 나라의 화폐 체계는 단순하다. 
이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다.

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

식으로 나타내면 0보다 크거나 같은 모든 K에 대해서 10^K인 동전과 25*100^K인 동전이 있다.

이기훈은 이 나라에서 새로운 차를 한 대 사려고 한다. 
이기훈은 차를 살 때, 가능하면 동전의 개수를 최소로 하려고 한다. 
이기훈이 필요한 동전 개수의 최솟값을 출력하는 프로그램을 작성하시오. 
(모든 값의 동전의 개수는 무한하고, 차를 살 때 정확하게 차의 값만큼 지불해야 한다.)

문제보기

🖨 입출력

📝 풀이

coins = [1, 10, 25]
dp = [float('inf') for _ in range(100)]
dp[0] = 0

for cost in range(100):
    for coin in coins:
        if cost + coin >= 100: continue
        dp[cost + coin] = min(dp[cost + coin], dp[cost] + 1)

for tc in range(1, int(input()) + 1):
    car_cost = int(input())

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

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/1398