백준 2293번 동전 1 (C++)

 다이나믹 프로그래밍 문제는 정말 어려운 것 같다. 

일단 모든 문제를 거의 O(N)으로 처리해야하는 엄청난 부담감과 아이디어.. 어쨌든 이 문제는 제한시간 0.5초로 매우 빡빡하다.

먼저 생각해볼 수 있는 DP 갱신은 두가지가 있다.

 

주어진 예제를 들면

3 10

1 2 5

먼저 DP[N] 에서 주어진 동전들로 N을 만들 수 있는 경우의 수를 저장하는 방법이 있을 것이다.

DP[1] = 1 

DP[2] = 2

DP[3] = 2

.

.

.

DP[10] = 10 

 이 방법이 가능하다면 O(N)의 방법으로 해결이된다. 그러나 이 방법은 완벽한 점화식을 찾아낼 수 없었다. 왜냐하면 계속해서 입력값이 달라지기 때문이다. 그러니 이 방법은 틀렸다.

 

두번째 DP 갱신은 DP[N] 에서 N까지의 동전을 사용했을 때 몇번의 방법이 있는가 테이블을 계속 갱신하는 것이다.

동전 1만 사용 했을 때 :

dp1	dp2	dp3	dp4	dp5	dp6	dp7	dp8	dp9	dp10
1	1	1	1	1	1	1	1	1	1

동전 1,2 까지 사용 했을 때:

dp1	dp2	dp3	dp4	dp5	dp6	dp7	dp8	dp9	dp10
1	2	2	2	3	3	3	4	4	5

동전 1,2,5 까지 사용했을 때:

dp1	dp2	dp3	dp4	dp5	dp6	dp7	dp8	dp9	dp10
1	3	3	3	5	6	7	8	9	10

이렇게 갱신된다. 즉 DP[i] = DP[i] + DP[i - 현재코인] 의 점화식을 얻을 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int DP[10001] = { 0, };
vector<int> coin;

int main() {	
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		coin.push_back(tmp);
	}

	DP[0] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = coin[i]; j <= k; j++) {
			DP[j] = DP[j] + DP[j - coin[i]];
		}
	}
	cout << DP[k];
}