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

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

9084번: 동전

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/20

[ 백준 ] 12865번 - 평범한 배낭 (C++)

 

1. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.

 

2. dp[ N ][ M ] 을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int T, N, M;
int arr[21];
int dp[21][10001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            dp[i][0] = 1;
            for (int j = 1; j <= M; j++) {
                dp[i][j] = 0;
            }
        }
 
        cin >> M;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (j < arr[i]) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
                }
            }
        }
 
        cout << dp[N][M] << '\n';
    }
}