[BOJ] 백준 2294번 - 동전 2 (Python)

문제

문제 바로가기

해결

이 문제는 그리디에서 나왔던 거스름돈 문제와 거의 동일하지만 화폐를 임의로 설정할 수 있으므로 화폐 단위에서 큰 단위가 작은 단위의 배수가 확정이 아니라는 점이 다르다. 그렇기 때문에 그리디 알고리즘처럼 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고, 다이나믹 프로그래밍을 이용해야한다.

이 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다.

금액 i를 만들 수 있는 최소한의 화폐 개수를 ai, 화폐의 단위를 c라고 할때 다음과 같이 점화식을 작성할 수 있다.

• a(i-c)를 만드는 방법이 있을 경우 : ai = min(ai, a(i-k) + 1)
• a(i-c)를 만드는 방법이 없을 경우 : ai = 10001

첫 번째 제출 (정답)

import sys

input = sys.stdin.readline

coins = []
n, k = map(int, input().split())
for _ in range(n):
  coins.append(int(input().strip()))

d = [10001] * (k + 1)
d[0] = 0

for coin in coins:
    for i in range(coin, k + 1):
        if d[i - coin] != 10001:
            d[i] = min(d[i], d[i-coin] + 1)

print(d[k] if d[k] != 10001 else -1)

위 코드는 화폐 단위를 하나씩 정한 뒤 해당 화폐 단위 c부터 k까지 반복문을 계속 도는 코드이다.

두 번째 제출 (정답)

import sys

input = sys.stdin.readline
coins = []

n, k = map(int, input().split())
for _ in range(n):
  coins.append(int(input().strip()))

coins.sort()

d = [10001] * (k + 1)
d[0] = 0

for i in range(1, k + 1):
  for c in coins:
    if i % c == 0:
      d[i] = i // c
    else:
      if i - c >= 0:
        d[i] = min(d[c] + d[i - c], d[i])

print(d[k] if d[k] != 10001 else -1)

위 코드는 1부터 k까지 반복문을 돌아가는 사이사이에 coins의 모든 화폐들 중 큰 화폐 순으로 나누어 떨어지는 지 검사하고, 나누어 떨어지지 않을 경우는 가장 큰 화폐부터 d[해당 가격- 큰 화폐] + d[큰 화폐]로 설정한다.