[DP] 백준 2294 동전2 C++

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

2294번: 동전 2

---

---

풀이 :

n 가지 동전으로 합이 k원이 되는 동전의 최소갯수를 구하는 문제

비슷한 문제로는 유명한 배낭문제랑 비슷하다. 

 

coins배열 : n개의 동전 종류 1원부터 시작하기위해 0번인덱스는 0으로두고 1부터 n까지 동전 설정

dp 배열 : dp[n] = 가치가 n원일 때 동전의 최소 갯수

 

예를 들어 설명하면 동전이 n원일때(coin[] 에서 가져오면 됨) 가치가 k면 k-n원의 최소 갯수를 이용해서 구하면된다

input : 

2 6

2

4

일 때

(초기 dp배열은 나올 수 있는 최대값인 10001로 설정해둔 상태, 0원을 만들 수 없기 때문에 dp[0]=0으로 초기 설정)

코드와 상관없이 상식적으로 채워보면 2원일 때 dp배열 상태가 이렇게 됨

	0	1	2	3	4	5	6
2원	0	max	1	max	2	max	3
4원

 

4원의 경우 4보다 작은 경우에는 영향을 주지 않는다

	0	1	2	3	4	5	6
2원	0	max	1	max	2	max	3
4원					1	max	2

가치가 4일때 4원짜리 하나

6일때는 4원짜리 하나 + 2원짜리 하나

 

위와 같은 과정으로 점화식을 세워보면

dp[가치 - 현재 동전의 값]+1인 식을 세울 수 있다.

위 점화식을 말로 풀어 보면 가치가 6일때 4원을 하나 쓰면 2원이 남으므로 dp[2]인 경우에 +1(4원하나 뽑았으니까)하는 거라고 생각하면 된다.

코드 :

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

int n, k;
int dp[10001];
int coins[101];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	dp[0] = 0;

	cin >> n >> k;

	for (int i = 1; i <= n; i++) cin >> coins[i];
	for (int i = 1; i <= k; i++) dp[i] = MAX;

	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);
		}
	}
	int answer = dp[k] == MAX ? -1 : dp[k];
	cout << answer  << endl;

	
}