백준 9048번 동전 [C++]

 

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

9084번: 동전

#문제 해결 방법

 

간단하게 생각해보자

일단 시간복잡도를 계산하고 브루트 포스는 안된다는 결론을 내릴 수 있다.

그렇다면 dp를 사용해야 하는데

dp는 큰 문제를 작은문제로 쪼갤 수 있으며 

작은 문제를 통해 큰 문제를 풀 수 있어야 한다

 

즉 dp[i][j] 는 i번째 동전을 사용해서 j 의 값을 만드는 횟수인데

이 횟수는

i번째 동전을 사용하지 않은 문제로부터 답을 구할 수 있다. (작은문제에서 큰 문제의 해답을 구하기)

즉 i-1 번째 동전을 사용하고 j-coins[i] (동전의 값) 인 경우의수에서 

더해주면 답을 구할 수잇다.

 

이로부터 도출되는 점화식은 

for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i]) {
                    dp[i][j] += dp[i][j - coins[i]];
                }
            }
        }

인 것이다.

 

#전체 코드

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

typedef long long ll;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;

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

        int M;
        cin >> M;

        vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0));
        for (int i = 0; i <= N; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i]) {
                    dp[i][j] += dp[i][j - coins[i]];
                }
            }
        }

        cout << dp[N][M] << '\n';
    }

    return 0;
}