[BOJ] 3067 - Coins (C++)

문제

Coins

코드

#include <iostream>
#include <cstring>

using namespace std;

int T, N;
int coin[21], arr[10001];

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> T;
    for (int test_case = 0; test_case < T; test_case++){
        cin >> N;
        memset(coin, 0, sizeof(coin));
        memset(arr, 0, sizeof(arr));

        for (int i = 0; i < N; i++) cin >> coin[i];
        int target;
        cin >> target;
        
        arr[0] = 1;
        for (int i = 0; i < N; i++){
            for (int j = coin[i]; j <= target; j++){
                arr[j] += arr[j-coin[i]];
            }
        }
        cout << arr[target] << "\n";
    }
    return 0;
}

접근

사실 동전 문제의 경우 어느 정도 정형화 된 것 같다.

arr[i] : 금액 i 를 만들 수 있는 경우의 수

금액 0의 경우 1가지의 경우의 수이므로 arr[0] = 1로 초기화를 해주었다. 현재 금액을 기존 금액에서 특정 동전을 추가로 사용했을 때 만들 수 있는지, 그 가짓수를 세주면 되기 때문에 모든 동전에 대해 값을 살펴보고 값을 더해주었다.

for (i : 코인 인덱스)
	for (j : coin[i] ~ 타켓 금액)
        	arr[j] += arr[j-coin[i]);