백준 2293번 동전 1 C++

출처 : https://www.acmicpc.net/problem/2293

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

 

top-down 방식으로 생각해 보면, 우선 예제에서 우리가 찾아야 할 최종 답은 1,2,5 동전을 이용해 10을 만들 수 있는 경우의 수를 찾는 것이다.

이것을 부분적인 문제로 나눠보면, 왼쪽은 5원을 한개 포함시킨 것이다. 5원을 포함시켰지만 또 포함시킬 수 있기 때문에 쓸 수 있는 동전은 같고, 10원에서 5원을 빼서 1,2,5를 사용해서 5원을 만들 수 있는 경우의 문제로 나눴다.

오른쪽은 5원을 포함시키지 않는 경우이다. 그렇기 때문에 1,2를 사용해서 10원을 만들 수 있는 경우의 문제로 나눴다.

여기서 알아낼 수 있는 점화식은 dp[i][j] = dp[i][j - v[i]] + dp[i-1][j] 이다. (v는 동전의 가치의 배열)

하지만 j가 v[i]보다 작을 경우 왼쪽으로 나눠질 수 없으니 dp[i][j] = dp[i-1][j]이고,

j와 v[i]가 같다면 왼쪽으로 나눠져서 나올 수 있는 답은 단 하나이기 때문에 dp[i][j] = 1 + dp[i-1][j] 이다.

 

이렇게 구한 점화식으로 2차원 dp테이블을 만들어서 제출했지만 이 문제의 메모리 제한이 4MB여서 메모리 초과가 났다. 그래서 last_dp, curr_cp 두 개의 1차원 dp테이블을 만들어서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;
	vector<int> v(n + 1, 0);
	vector<int> dp_last(k + 1, 0);
	vector<int> dp_curr(k + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	for (int i = 1; i <= k; i++) {
		if (i % v[1] == 0) {
			dp_last[i] = 1;
			dp_curr[i] = 1;
		}
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j < v[i]) {
				dp_curr[j] = dp_last[j];
			}
			else if (j == v[i]) {
				dp_curr[j] = dp_last[j] + 1;
			}
			else {
				dp_curr[j] = dp_curr[j - v[i]] + dp_last[j];
			}
		}
		for (int j = 1; j <= k; j++) {
			dp_last[j] = dp_curr[j];
		}
	}
	cout << dp_curr[k];
};