[Baekjoon] 2294. 동전 2

🔗 Problem Link

https://www.acmicpc.net/problem/2294

---

❔Thinking

• n개 종류의 동전을 활용해서, k원을 만드는 최소한의 동전 개수를 반환한다. k원을 만들 수 없다면 -1을 반환한다.
• 1<= n <= 100, 1<= k <= 10,000

---

💻Solution

1. DP를 활용한 풀이

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input().rstrip()))
coins.sort()
answer = [float('inf') for _ in range(k+1)]
answer[0] = 0
for i in range(1, k+1):
    for coin in coins:
        if i-coin >= 0:
            answer[i] = min(answer[i], answer[i-coin]+1)
print(answer[k] if answer[k]!=float('inf') else -1)

 

2. BFS를 활용한 풀이

import sys
from collections import deque

def coin_change_bfs(N, K, coins):
    queue = deque([(0, 0)])
    visited = set([0])

    while queue:
        current, count = queue.popleft()
        
        if current == K:
            return count

        for coin in coins:
            next_amount = current + coin
            if next_amount <= K and next_amount not in visited:
                visited.add(next_amount)
                queue.append((next_amount, count + 1))
    return -1

N, K = map(int, sys.stdin.readline().split())
coins = [int(sys.stdin.readline().strip()) for _ in range(N)]

print(coin_change_bfs(N, K, coins))

---

🗝️keypoint

1. DP를 활용하는 경우 : 각 동전의 가치를 더해서 현재 가치를 만들 수 있는 최소값을 갱신한다.
2. BFS를 활용하는 경우 : 모든 금액을 만드는 방법을 확인하고, k인 경우 반환한다.