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

문제

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

문제 이해

N가지 동전으로 금액 M을 만드는 모든 방법의 수를 구한다.

문제 풀이

🔍 접근

이 문제는 대표적인 Unbounded Knapsack 문제다.

아래의 배낭 문제에서 각 물건을 1번만 선택할 수 있었던 점과 다르게, 같은 동전을 여러번 넣을 수 있다.

[BOJ][C++] 백준 12865번: 평범한 배낭

 

💡 Dynamic Programming

• 목표 금액을 인덱스로, 목표 금액을 만드는 방법의 수를 저장한다.
• 작은 금액을 만드는 방법부터 채워나간다.
• 0원을 만드는 방법의 수는 1이다.

dp[0] = 1

💡 Bottom-up DP

j를 만들기 위한 조합 = (j - coin) 조합 + coin 하나 더

for (int coin: coins) {
        for (int j = coin; j <= m; j++)
            dp[j] += dp[j - coin];
    }

코드

#include <iostream>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> &coins) {
    vector<int> dp(m + 1, 0);
    dp[0] = 1;

    for (int coin: coins) {
        for (int j = coin; j <= m; j++)
            dp[j] += dp[j - coin];
    }

    return dp[m];
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m;
        vector<int> coins;

        // 입력
        cin >> n;
        coins.assign(n, 0);
        for (int &i: coins)
            cin >> i;
        cin >> m;

        // 출력
        cout << solution(n, m, coins) << '\n';
    }

    return 0;
}