C++ [BOJ] 백준 2294번 동전 2

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

2294번: 동전 2

---

SOLUTION

DP배열에 답을 구할건데, 최소값을 찾아야 하니까 우선 매우 큰 수로 초기화 한다.

초기의 배열 상태는 다음과 같다.

Idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF

예제에서는 1,5,12원짜리 동전들이 있는데 먼저 1원짜리로 n원을 만드는 경우는 이렇게 만들 수 있다.

Idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

 

1원으로 1을 만드는 방법의 수는 dp[1-1]+1로 1이 나오고, 2를 만드는 방법의 수는 dp[2-1]+1로 2가나온다.

같은 방식으로 5원의 경우에는

Idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3

 

다음과 같이갱신이 된다.

dp[5]=dp[5-5]+1=1이고, dp[6]=dp[6-5]+1=2이다.

Idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
12원	0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	4

 

dp[12]=dp[12-12]+1=1, dp[13]=dp[13-12]+1=2

 

점화식 dp[j]=dp[j-coins[i]]+1이 나오고, 코드는 다음과 같다.

---

코드

#include <iostream>
#include <algorithm>
#define MAX 10001
#define INF 123456789
using namespace std;

int coins[MAX];
int dp[MAX];

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> coins[i];
	}
	for (int i = 1; i <= k; i++) {
		dp[i] = INF;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = coins[i]; j <= k; j++) {
			dp[j] = min(dp[j], dp[j - coins[i]] + 1);
		}
	}
	if (dp[k] == INF) cout << -1;
	else cout << dp[k];
}