[백준] 9084 동전

배낭 관련 문제들 2문제를 풀고 약간의 고뇌의 시간(?)을 보내니까 약간 어느 정도 감이 올 듯 말 듯 한 거 같다.

 

예제로 나온 수들은 너무 크기 때문에 내 마음대로 돈의 크기를 대폭 줄여서 생각해 보았다.

 

N= 3, M= 20

동전의 종류: 1, 5, 10

n=5인 행의 10열 에 해당하는 숫자 3은 5원, 1원짜리 동전으로 구성할 수 있는 경우의 수를 계산한 값이다.

배낭 문제에서 흔히 나오는 방식은 j-array[i]를 이용하니 쉽게 규칙을 파악할 수 있었다..

 

 

□ 소스 코드

#include <bits/stdc++.h>

using namespace std;

void coin9084(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int testCase; cin>>testCase;
    
    for(int t=0; t<testCase; t++){
        int N; cin>>N;
        
        int array[N+1];
        for(int i=1;i<=N;i++)
            cin>>array[i];
        
        int M; cin>>M;
        int dp[N+1][M+1];
        
        for(int i=0; i<=N;i++)
            for(int j=0; j<=M;j++)
                dp[i][j] = 0;
        
        for(int i=1; i<=N;i++){
            for(int j=1; j<=M;j++){
                if (j == array[i])
                    dp[i][j] = dp[i-1][j] + 1;
                else if(j - array[i] >= 0){
                    dp[i][j] = dp[i][j-array[i]] + dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        cout<<dp[N][M]<<endl;
    
    }
    
}