백준 9084번, 동전(C, C++)

9084번: 동전 (acmicpc.net)

9084번: 동전

 

다이나믹 프로그래밍(DP)으로 문제를 해결하였습니다.

 

 

 

간단한 예시로 {1원, 2원, 3원} 3종류의 동전이 있습니다.

0원의 값을 만들기 위해서는 아무것도 사용하지 않는 경우 1가지가 있습니다.

 

1원의 값을 만들기 위해서는 1원 한 가지의 경우입니다.

2원의 값을 만드는 경우는  1+1, 2   2가지가 있습니다. 

3원의 값을 만드는 경우는  1+1+1 , 1+2, 3이 있습니다.

 

위 그림을 자세히 살펴보면 1원, 2원, 3원 ,4원을 만드는데 1원이 무조건 들어갑니다.

기본적으로 1원으로 만드는 경우의 수 1가지가 무조건 들어간 다는 것을 알 수있죠.

그러면 기본적으로

dp[1] ~ dp[4] = 1이라는 경우의 수를 가질 것입니다.

2원이라는 동전을  사용하면,  1가지 경우의 수가 늘어 dp[2] = 2가 될 것이고,

dp[3] 또한 2가지의 경우의 수를 가질 것 입니다.

dp[4] 또한 1 + 1 + 2와 2 + 2 라는 경우의 수가 추가 되어 dp[4] = 3이 됩니다.

다시 돌아가 3원을 추가하여 1~4원을 만드는 경우를 살핍니다.

dp[1], dp[2]는 3원이 들어갈 수 없습니다.

dp[3]은 3원짜리로 만드는 경우의 수를 추가하여 3가지의 경우의 수를 이룹니다.

dp[4]는 1+3인 경우가 추가되어 4가지를 만들어집니다.

위 그림 순서처럼 흘러갑니다.

 

그림을 살펴보면,.

1원만 사용한 4원을 만드는 경우의 수 더하는 사이클이 돌고나면, 2원을 사용한 4원을 만드는 사이클이 돌고, 3원을 사용한 4원 사이클이 돌면서 끝이납니다.

 

아래는 다음을 코드로 구현한 것 입니다. 

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

int main(){
    int T;
    int N;
    int M;
    int arr[21];
    int dp[10001];
    cin>>T;
    while(T--){
        memset(dp, 0, sizeof(dp));
        cin>>N;
        for(int i = 1; i <= N; i++){
            cin>>arr[i];
        }
        cin>>M;
        dp[0] = 1;
        for(int i = 1; i <=N; i++){
            for(int j = arr[i]; j <= M; j++){
                dp[j] += dp[j - arr[i]]; 
            }
        }
        
        
        cout<<dp[M]<<'\n';
    }
    return 0;
}