[백준/C++] #2293 동전1 (DP)

문제

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

구상

나는 보통 문제를 보고 '어떻게 접근해야 할지 모르겠다...! 혹은 재귀인가..?'라는 생각이 들면 dp로 접근해본다. 이 문제도 그러했다. 오랫만에 dp를 풀어서 그런지 좀 머리를 싸맸는데, 동전의 구성이 같은데, 순서만 다른 것은 같은 경우라는 조건을 보고 동전의 가치를 큰 기준으로 잡고 가야겠다는 생각이 들었다. 글로 쓰기가 어려워서 그림으로 대체한다. 

 

알고리즘

이전에 구한 값을 이용하여 다음 값을 구하기에 dp(dynamic programming)를 이용했다. 

풀이 + 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\n"
using namespace std;

int N, K;
vector<int> coins;
vector<int> dp;

void solution() {

    dp[0] = 1; // 가치가 0일 때의 경우의 수는 1 (아무 동전도 사용하지 않는 경우)

    for (int j = 0; j < coins.size(); j++) { // 각 동전에 대해
        for (int i = coins[j]; i <= K; i++) { // 해당 동전의 가치부터 시작하여 K까지
            dp[i] += dp[i - coins[j]]; // dp[i]에 dp[i - 동전의 가치] 값을 더함
        }
    }
    
    cout << dp[K] << endl; // K가 될 때의 경우의 수 출력
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // 입력
    cin >> N >> K; // 동전의 종류 개수, 가치의 합
    coins.resize(N);
    dp.resize(K + 1, 0);

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

    // 로직
    solution();

    return 0;
}