[BOJ 9084] 동전

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

9084번: 동전

 

 

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 구해야 한다.

 

 

 

 

x를 임의의 동전의 값이라고 할 때,

 

 

 

 

dp[M] += dp[M - x]로 식을 세우면 엄청 큰 값이 나오게 된다. 확인해보면, 중복된 방법의 수가 더해지게 된다.

 

 

 

 

수를 나열하면서, 규칙을 다시 찾아봐야 한다.

 

 

 

 

1원만으로 만드는 가짓수를 살펴보자.

 

 

 

 

1 = (1)

2 = (1, 1)

3 = (1, 1, 1)

4 = (1, 1, 1, 1)

5 = (1, 1, 1, 1, 1)

 

 

 

 

 

1원과 2원으로 만드는 가짓수를 살펴보자.

 

 

 

 

1 = (1)

2 = (1, 1), (2)

3 = (1, 1, 1), (2, 1)

4 = (1, 1, 1, 1), (2, 1, 1), (2, 2)

5 = (1, 1, 1, 1, 1), (2, 1, 1, 1), (2, 2, 1)

 

 

 

 

5에서 (2, 1, 1, 1), (2, 2, 1)은 3에서 만들어질 수 있는 조합에 2만 포함시킨 것으로 볼 수 있다.

 

 

 

 

따라서, 이미 만들어진 조합에 동전 하나를 더 추가하면서 값을 갱신해야 한다.

 

 

 

 

해설코드(C++).

 

#include <iostream>

#include <cstring>

 

using namespace std;

 

int T, N, M;

int coin[21];

int dp[10001];

 

int main() {

    cin >> T;

    for(int i = 1; i <= T; i++){

        cin >> N;

        for(int j = 1; j <= N; j++){

            cin >> coin[j];        

        }

        

        cin >> M;

        memset(dp, 0, sizeof(dㅊ ㅍp));

        

        dp[0] = 1;

        for(int c = 1; c <= N; c++){

            for(int j = 1; j <= M; j++){

                if(j - coin[c] >= 0)

                    dp[j] += dp[j - coin[c]];

            }

        }

        

        cout << dp[M] << endl;

    }

    return 0;

}