[백준 3067번] Coins (C++)

문제링크 : https://www.acmicpc.net/problem/3067

3067번: Coins

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N, M;
int arr[21];
int dp[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    while(T--)
    {
        cin >> N;
        for(int i=0; i<N; i++)
        {
            cin >> arr[i];
        }
        cin >> M;
        memset(dp, 0, sizeof(dp)); //케이스마다 초기화
        dp[0]=1; //첫 값 초기화
        for(int i=0; i<N; i++) //동전 갯수
        {
            for(int j=arr[i]; j<=M; j++) //합
            {
                dp[j] = dp[j] + dp[j-arr[i]]; //점화식
            }
        }
        cout << dp[M] << "\n";
    }
    
}

유사한 타입이 많은 배낭 문제이다.

해당 문제는 테스트케이스가 여러가지이기 때문에 dp식을 매 테스트마다 초기화를 해주어야한다.

동전의 가짓수를 담은 arr 배열은 N과 내용을 새로 입력 받기 때문에 초기화를 할 필요가 없다.