[C++] 백준 9084번: 동전

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

9084번: 동전

 

 

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t,n,m;
    cin>>t;
    
    for(int i=0;i<t;i++){
        int dp[10001]={1,0};
        int coin[21];
        cin>>n;
        for(int j=1;j<=n;j++){
            cin>>coin[j];
        }
        cin>>m;
        for(int j=1;j<=n;j++){
            for(int q=coin[j];q<=m;q++){
                dp[q]+=dp[q-coin[j]];
            }
        }
        
        cout<<dp[m]<<"\n";
    }
    
    return 0;
}

 

 

[설명]

예를들어

m=10, coin 값으로 2,5,6을 입력 받았을 때, 

m의 값이 0인 경우 2,5,6은 모두 하나의 경우의 수를 가진다. (아무것도 안내는 경우)

제일 작은 값을 가진 2원은 2의 배수를 가질때만 1번의 경우의 수를 가진다.(2원으로 모두 다 내는 경우) 그 외는 모두 0을 넣는다.

 

coin이 5원일 경우, 돈이 4원일때까지는 5원를 가지고 나올수있는 경우의 수가 없기 때문에 2원일 때의 값을 그대로 가진다.

 

 

m의 값이 5이상이 되면 5원 동전으로 낼 수 있는 경우의 수가 생긴다!

따라서 m이 5일 경우, 2원(coin에서 5원보다 작은 값 모두)으로 만들수있었던 경우의 수와 5원 동전으로 낼 수 있는 경우의 수를 더한다.

 

마지막 coin값까지 구해보면 총 경우의 수는 3가지가 나온다.

 

 

 

 

 

[참고자료]

https://yabmoons.tistory.com/556

[ 백준 9084 ] 동전 (C++)

>> 이분의 case예시가 이해하는데 매우 도움이 되었다!