Problem 2.3.4 Money Systems

출처: https://train.usaco.org/usacogate

---

문제 설명

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 of {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 using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).

입력 양식

The number of coins in the system is V (1 <= V <= 25).
The amount money to construct is N (1 <= N <= 10,000).

Line 1: Two integers, V and N
Lines 2..: V integers that represent the available coins (no particular number of integers per line)

출력

A single line containing the total number of ways to construct N money units using V coins.

입력 예

3 10 
1 2 5

출력 예

10

---

문제 풀이

특정한 정수 집합으로 원하는 값을 만들어내는 경우의 수를 세는 문제로 coin change 문제이다. 

특정한 코인 값 c[i] =a 라고 하면, 원하는 값 target 를 만들 수 있는 방법은 이 코인이 없이 만들수 있는 경우의 수와 이 코인 값을 제외한 값을 만들수 있는 경우의 수의 합이 된다. 

	...	target - b	...	target	...
coin[i] = a	...	...	...	v(target, a)	...
coin[i+1] = b	...	v(target - b, b)	...	v(target, b)	...

 v(target, b) = v(target, a) + v(target-b, b) 

다만, 이 경우에는 코인의 수는 제한이 없기 때문에, 코인 값의 배수들에 해당하는 값들을 모두 확인해야 한다.

참고: subset sum problem ( link )

프로그램 내용

int main()
{
    int N, target;
    fin >> N >> target;

    vector<int> coins(N,0);

    for (int id = 0; id < N; ++id) 
        fin >> coins[id]; 

    vector <long long> table(target+1,0);

    sort(coins.begin(), coins.end());

    table[0] = 1;

    for(int id = 0; id < N; ++id) 
        for(int idn = coins[id]; idn <= target; ++idn) 
            table[idn] += table[idn-coins[id]]; 

	if( table[target] != 0) 
        fout << table[target] << '\n'; 
    else 
        fout << -1 << '\n'; 

 

Chapter 2. Bigger Challenges ( link )