[백준] 9084번 동전

[적용한 알고리즘]

DP

 

[아이디어]

중복을 없애주기 위해, 

첫번째 동전을 이용하는 경우를 다 더해주고,

두번째 동전을 이용하는 경우를 다 더해주고,

세번째 동전을 이용하는 경우를 다 더해주고,

쭉쭉 더해주면 된다.

 

[교훈]

중복 없애는 테크닉이 상당히 아름다웠다.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;


int main(){
    int t;
    scanf("%d", &t);

    while (t--){
        int N, M;
        int dp[10001] = { 0 };
        scanf("%d", &N);

        int coin[21] = { 0 };

        for (int i = 0; i < N; i++){
            scanf("%d", coin + i);
        }

        sort(coin, coin + N);
        scanf("%d", &M);

        dp[0] = 1;

        for (int i = 0; i < N; i++){
            for (int j = coin[i]; j <= M; j++){
                dp[j] += dp[j - coin[i]];
            }
        }

        printf("%d\n", dp[M]);
    }
    return 0;
}