[C++][백준] - 동전 -1 (2293번)

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

2293번: 동전 1

🔔 문제 : 

(1<= n <= 100)인 n가지 종류의 동전이 있습니다.

 

이 동전을 사용하여, 가치의 합이 (1<= k <= 10000) k원이 되도록 하는 경우의 수를 구하는 문제입니다.

 

동전의 가치는 100,000보다 작거나 같은 자연수입니다.

---

🔔 Kick Point :

DP 문제이고, Bottom-up 형식으로 O(n*k) 시간복잡도를 만들어 풀었습니다.

 

우선, 예를들어 n= 3 k= 10이고

동전이 2, 3, 5 인 동전이 있다고 들어보겠습니다.

 

이때, 10원을 만들기 위해서는 F(10) = F(10 - 2) + F(10 - 3) + F(10 - 5) 의 경우의 수를 계속 구하면 됩니다.

즉 F(k) = n개의 동전들의 F(k - 동전의 가치)의 합 인 셈이 됩니다.

이를 bottom-up 방식으로 F(1)부터 F(k) 까지 계속 구해가면 됩니다.

---

🔔 Code :

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

int main() {
	int n, k; cin >> n >> k;
	
	vector<int> v(n);
	vector<int> dp(k + 1);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	dp[0] = 1;
	for (int i = 0; i < v.size(); i++) {
		for (int j = v[i]; j <= k; j++) {
			dp[j] = dp[j] + dp[j-v[i]];
		}
	}
	cout << dp[k];
}

---