[Python] 백준 1398 동전 문제

문제 링크 : https://www.acmicpc.net/problem/1398

1398번: 동전 문제

1. 접근 방법

기본적인 접근은 거스름돈 문제처럼, 해당 금액을 가장 큰 금액으로 채우는 것으로 시작했다.

그런데, 10과 25가 약수 / 배수 관계가 아니라서 일반적인 방법으로 해결하지 못한다.

(30일 때, 10 + 10 + 10이 최소이지만, 큰 값 부터하면 25 + 1 + 1+ 1+ 1+ 1으로 최소가 아니게 됨)

그래서 전반적인 틀은 거스름돈 문제로, 그리고 10과 25꼴으로 따로 처리해야되면 그리디하게 구간은 나누어 처리했다.

 

 

2. 풀이 코드

🖥python

import sys
input = sys.stdin.readline

coins = [10 ** i for i in range(16)] + [25 * (100 ** i) for i in range(7)]
coins.sort(key=lambda x:-x)

# 0 ~ 100일때 최소 비용
costs = [100] * 101
costs[0] = 0
# 10의 배수일 때
for i in range(1, 11):
    costs[i * 10] = i
# 25의 배수일 때
for i in range(1, 5):
    costs[i * 25] = i
    # 추가적 10의 배수 더할 때
    for j in range(1, 10):
        if i * 25 + j * 10 > 100:
            break
        costs[i * 25 + j * 10] = i + j
# 나머지 값
for i in range(1, 100):
    if costs[i - 1] + 1 < costs[i]:
        costs[i] = costs[i - 1] + 1

for _ in range(int(input())):
    # 2자리씩 계산
    n = input().strip()
    n = n.zfill((len(n) // 2 + 1) * 2)
    
    total_count = 0
    for i in range(len(n) // 2):
        m = n[i * 2:(i + 1) * 2]
        total_count += costs[int(m)]
    print(total_count)

📕풀이 과정

25로 시작되는 값의 동전은 100씩 곱해지며 값이 생긴다.

즉, 25, 2500, 250000... 으로 생기게 되고, 금액을 탐색할 구간을 똑같이 두자리씩 확인해도 된다.

예를 들어 6020이라는 값이 들어오면, 6000과 20으로 나누고, 6000에 해당하는 값은 100, 1000, 그리고 2500 세 값으로 확인한다. 같은 방식으로 20도 1, 10과 25 세 값만 확인하면 된다.

 

 

3. 생각 정리

가끔은 이렇게 단순할 수 있는 문제에서 쉽게 틀릴 수 있는 부분에 너무 잘 빠진다.

역시 문제를 잘 읽어야 겠다는 생각도 들지만, 동시에 그리디 문제의 다양한 문제를 경험해보는 것도 좋을 것 같다.