[BOJ] Cow Cash 6126번 C++

 

문제

The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.

The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems.  For instance, using a system with values {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.

Write a program to compute how many ways to construct a given amount of money N (1 <= N <= 10,000) using V (1 <= V <= 25) coins. It is guaranteed that the total will fit into both a signed 'long long' integer (C/C++), 'Int64' (Pascal), and 'long' integers in Java.

입력

• Line 1: Two space-separated integers: V and N
• Lines 2..V+1: Each line contains an integer that is an available coin value

출력

• Line 1: A single line containing the total number of ways to construct N money units using V coins

 

접근 방식

 

0/1 knapsack 문제와 비슷하지만, 코인이 중복 선택이 가능하다는 점에서 완전 배낭 문제로 볼 수 있다

따라서 dp[i]를 금액 i를 만드는 방법의 개수로 정의하고

각 동전을 순회하면서 현재 동전을 사용해서 만들 수 있는 모든 금액을 업데이트해주면 된다!

단, 중복을 허용하기 때문에 앞에서부터 dp를 갱신해야 한다!!

 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[10005]; // dp[i] = 여러 동전을 이용해 i원을 만드는 경우의 수
int main() {
    int V,N; cin>>V>>N;
    
    dp[0] = 1;

    for(int i=0; i<V;i++) {
        int coin; cin>>coin;

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

    cout<<dp[N];
}