문제
풀이
•
n 개의 코인으로 k 값을 만들수있는 경우의 수를 구하는 문제
•
순서에 상관없이 종류가 중요하기 때문에
•
이미 계산한 코인은 더이상 계산하면 안된다.
•
즉, 코인 순서대로 처리해줘야한다.
•
예를들어 1 을 처리했으면 그다음은 2, 5 를 처리해야지 1을 다시 처리 5 를 처리해야지 1을 다시 처리하면 안된다.
•
이게 재귀로는 도무지 못하겠다. ㅠ
구현
#include <iostream>
#include <vector>
using namespace std;
int n;
int k;
vector<int> coins;
vector<int> dp;
void pre() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void input() {
cin >> n >> k;
coins.resize(n);
for (int i = 0; i < n; i++)
cin >> coins[i];
dp.resize(k + 1);
for (int i = 0; i <= k; i++)
dp[i] = 0;
}
void solve() {
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = coins[i]; j <= k; j++)
dp[j] = dp[j] + dp[j - coins[i]];
cout << dp[k] << endl;
}
int main() {
pre();
input();
solve();
return (0);
}
C++
복사