[백준] DP 2293번 동전1 C++ 풀이

문제

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

 

동전1, 2로 두개 문제가 있는데 오랜만에 다시볼라니까 좀 헷갈려서 정리한다.

참고로 9084번 동전 문제도 똑같은 문제이다.

---

 

풀이

동전1의 경우 주어진 금액에 맞게 주어진 동전들을 이용해 만들 수 있는 경우의 수를 세는 것이다. 

여기서 생각해봐야할 점은 문제에도 나와있듯

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우

에는 동일한 경우의 수이다.

4원을 만들때, 1,3원짜리 화폐가 있으면 1+3이나 3+1이나 동일하다는 것이다.

이 두 경우를 다르게 본다면 DFS나 BFS를 이용할 수 있을 것이다.

 

여기선 동일한 경우로 따지기때문에, 1이 먼저오는 경우를 미리 판단한다고 생각한다. 그렇게한다면 DP배열의 1로가는 경우의 수를 먼저 대입한다. 

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

 

처음엔 coin 배열이 오름차순이어야 된다고 생각했는데, 어떤식의 정렬이든 1이 먼저인지 3이 먼저인지만 다를뿐 결과는 같다. 

 

 

 

---

 

소스코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 10001;
int n, k;
vector <int> coin;
int dp[10001];
int main(){
    cin >> n >> k;
    int num;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        coin.push_back(num);
    }
    dp[0] = 1;
    for (int i = 0; i < coin.size(); ++i) {
        for (int j = coin[i]; j <= k; ++j) {
            dp[j] = dp[j] +dp[j - coin[i]];
        }
    }

    cout << dp[k];
}