Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 2294 동전2
백준 2294 동전2
문제
n가지 종류의 동전이 있다.
이 동전들을 적당히 사용해 그 가치의 합이 k원이 되도록 하고싶다.
각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 최소 개수를 계산하는 프로그램을 작성하시오.
입력
- 첫째 줄: n, k
- 둘째 줄 ~ : 동전의 가치
출력
사용한 동전의 최소 개수
해결 방식
dp 알고리즘 이용
- dp[i]에 dp[i]원을 구성하는 동전의 최소 개수를 저장
과정
15원을 1, 5, 12원으로 구성할 경우
1. dp[1]
- 1원을 추가할 경우 = dp[0] (0) + 1 = 1
- 5원을 추가할 경우: 불가능
- 12원을 추가할 경우: 불가능
- 1개의 동전으로 구성하는 경우가 최소 개수
2. dp [2]
- 1원을 추가할 경우: dp[1] (1) + 1 = 2
- 5원을 추가할 경우: 불가능
- 12원을 추가할 경우: 불가능
- 2개의 동전으로 구성하는 경우가 최소 개수
…
5. dp[5]
- 1원 동전을 추가할 경우: dp[4] (4) + 1 = 5
- 5원 동전을 추가할 경우: dp[0] (0) + 1 = 1
- 12원을 추가할 경우: 불가능
- 5원 동전을 추가하는 경우가 최소 개수
6. dp[6]
- 1원 동전을 추가할 경우: dp[5] (1) + 1 = 2
- 5원 동전을 추가할 경우: dp[1] (1) + 1 = 2
- 12원을 추가할 경우: 불가능
- 5원 동전을 추가하는 경우가 최소 개수
…
14. dp[14]
- 1원 동전을 추가할 경우: dp[13] (2) + 1 = 3
- 5원 동전을 추가할 경우: dp[9] (5) + 1 = 6
- 12원 동전을 추가할 경우: dp[2] (2) + 1 = 3
- 3개의 동전으로 구성하는 경우가 최소 개수
15. dp[15]
- 1원 동전을 추가할 경우: dp[14] (3) + 1 = 4
- 5원 동전을 추가할 경우: dp[10] (2) + 1 = 3
- 12원 동전을 추가할 경우: dp[3] (3) + 1 = 4
- 3개의 동전으로 구성하는 경우가 최소 개수
코드
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coins = []
dp = [0] * (k+1)
for _ in range(n):
coins.append(int(input()))
for i in range(1, k+1):
comparison = []
for coin in coins:
if i >= coin and dp[i - coin] != -1:
comparison.append(dp[i - coin])
if not comparison:
dp[i] = -1
else:
dp[i] = min(comparison) + 1
print(dp[-1])
