[백준] 9084번 동전 C++

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

C++

#include<iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int test,num,money;
    cin >> test;

    while(test--) {
        int coin[21] = {0, };
        int dp[10001] = {0,};
        dp[0] = 1;
        cin >> num;
        for(int i = 0; i < num; i++) {
            cin >> coin[i];
        }
        cin >> money;

        for(int j = 0; j < num; j++) {
            for(int k = coin[j]; k <= money; k++) {
                dp[k] += dp[k - coin[j]];
            }
        }
        cout << dp[money] << "\n";
    }
}

문제풀이

• 동전 1 문제를 풀었다면 다소 쉽게 문제를 풀 수 있다. 동전의 종류가 주어지고 그 동전들로 주어진 금액을 만들 수 있는 총 경우의 수를 구하는 문제이다. 동전 1 문제 알고리즘과 똑같이 동전들의 배열인 coin과 주어진 금액을 만들 수 있는 경우의 수를 저장할 dp를 만든다. 그런 다음 dp[k] += dp[k - coin[j]]를 사용해서 k값을 만들 수 있는 경우의 수를 저장한다.

동전 1 문제풀이 : https://velog.io/@jaejun03/%EB%B0%B1%EC%A4%80-2293%EB%B2%88-%EB%8F%99%EC%A0%84-1-C

Comment

• 동전 1 문제를 푸는데는 꽤 오랜 시간이 걸렸었는데 그 알고리즘을 기억하고 이번 문제를 쉽게 풀어서 기분이 좋았다!!

알고리즘은 매일매일 꾸준히 하는게 진짜 중요중요