[Gold 5] 9084 동전

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

9084번: 동전

 

이 문제는 배낭을 이용한 dp 문제이다.

 

문제에서 주어지는 동전은 N개이며, 동전의 가치도 입력으로 주어진다.

 

예제 입력에 따르면 1원 2원의 동전을 통해 1000원을 만들어야한다.

이를 위해서는 1 1 1 .... 1에서 2 2 2 2... 2원까지 총 501가지의 경우의 수가 발생한다.

 

이 문제를 해결하기 위해서는 1원에서 1000원까지 1원의 동전과 2원의 동전으로 만들 수 있는 경우의 수를 합치는 방식을 사용해야한다.

즉, 1원을 통해 1원까지 만들 수 있는 방법은 1가지이며, 2원을 만들 수 있는 방법은 1가지 일 것이다.

또한 2원을 통해 1원은 만들 수 없고, 2원까지는 1가지, 4원까지는 1가지 일 것이다.

 

2원을 통해서는 완벽히 3원을 만들 수 없지만 이전에 사용한 1원을 가지고선 만들 수 있다.

이는 이전에 구한 1원의 경우의 수를 합치면될 것이다.

 

마지막으로 동전을 합쳐서 만드는 방식도 있을 것이다. 

예제를 통해 생각해보면 1원과 2원의 조합을 통해 4원을 만든다면 총 3가지의 경우의 수가 생긴다.

 

위에서 구한 생각을 통해 DP식을 새우면 아래와 같다.

DP[X] = DP[X] + DP[X - 현재 사용하는 동전 가치]

 

이러면 1원의 경우 1000까지 경우의수를 새우면 DP[1000]은 위에서 생각했던 것과 같이 1이 될 것이다.

이어서 2원의 경우는 2, 2, 3, 3, 4, 4, ..., 501의 경우의 수가 DP에 저장될 것이다.

이는 동전의 가치가 오름차순으로 정렬되어 있어서 가능한 방식이다. 만약 동전의 가치가 오름차순이 아니라면 정렬 후 사용해야하는 방법이다.

 

 

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

int T,N,M;
int coin[10001];
int dp[10001];
int target = 0;

void solve(){
    dp[0] = 1;
    for(int i = 0;i<N;i++){
        for(int j = coin[i];j<=target;j++)
            dp[j] += dp[j - coin[i]];
    }
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    // Test case input
    cin>>T;
    for(int i = 0;i<T;i++){
        memset(dp, 0, sizeof(dp));

        // coin input
        cin>>N; 
        for(int j = 0;j<N;j++)
            cin>>coin[j];
        
        // target value input
        cin>>target;

        // dynamic programming
        solve();
        cout<<dp[target]<<'\n';
    }
    
    
    return 0;
}