C++ / 백준 / 2293 / 동전 1

문제

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

2293번: 동전 1

 

문제풀이

처음에는 단순히 DP[10] = DP[10-1] + DP[10-2] + DP[10-5]를 하려고 했다.

하지만 이렇게 누적시키게 되면 숫자 구성은 같지만 순서만 다른 것도 포함이 되므로 틀린 답이다.

동전 단위 개수만큼 반복문을 돌리고, n원부터 k원 까지 DP[x] = DP[x-n]값을 누적시킨다.

처음 n원으로 n원을 만들때 DP[n]=DP[n-n]일 때, DP[0]의 값을 사용하므로 DP[0]=1으로 설정한다.

표로 보면 이해가 더 쉬울것같아 2개의 예시를 가져왔다.

 

1, 2, 5원의 동전을 가지고 6원을 만드는 경우

 

 

2, 4, 5원의 동전을 가지고 6원을 만드는 경우

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n = 0;
	int k = 0;
	int x = 0;
	int cnt = 0;
	cin >> n >> k;
	vector<int>DP(k + 1, 0);
	vector<int>coin(n, 0);

	for (x = 0; x < n; ++x) {
		cin >> coin[x];
	}

	DP[0] = 1;
	for (cnt = 0; cnt < n; ++cnt) {
		for (x = coin[cnt]; x <= k; ++x) {
			DP[x] += DP[x - coin[cnt]];
		}
	}

	cout << DP[k];
}