Search
Duplicate

동전 1 (2293)

생성일
2021/03/20 18:19
태그

문제

풀이

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++
복사