[C/C++] 프로젝트 오일러 #31 : 코인들의 합

영국에는 아래와 같은 동전 단위가 있습니다:
• 1p, 2p, 5p, 10p, 20p, 50p, 1파운드(100p), 2파운드(200p)

목표는 200펜스(2파운드)를 만들기 위해, 위 동전들을 활용한 서로 다른 조합의 수를 찾는 것입니다.

조건:
1. 동전은 필요한 만큼 반복적으로 사용할 수 있습니다.
2. 순서는 중요하지 않습니다. (즉, {1p, 2p}는 {2p, 1p}와 동일한 조합으로 간주됩니다.)
3. 중복된 조합을 제거한 고유한 조합의 수를 구해야 합니다.

---

 

이번문제는 재귀 함수를 만들어서 프로그램을 작성했습니다.

 

예를 들어서 200 파운드를 계산하기 위해서 첫번째 가장 큰 단위의 코인을 쓸 것인지부터 몇개를 쓸것인지 결정하여서 나머지 돈에 대해서 그 다음 단위의 코인을 이용하여 경우의 수를 따졌습니다.

 

코인의 금액을 200, 100, 50, 20, 10, 5, 2, 1 을 각각 \( coins_1 \quad - \quad coins_8\)으로 놓는다면, 경우의 수 \( Comb(n, i) \) 를 금액 n에 대하여 i 이상에 대한 코인으로 조합하는 경우의 수라고 한다면, 다음과 같이 재귀적인 표현이 가능합니다.

 

\[ Comb(n, i) = \sum_{k=0}^{n/coins_i} Comb(n-k \cdot coins_i , i + 1 ) \]

 

coin sum

 

이 방식을 이용해서 소스를 작성하면 다음과 같습니다.  소스는 참고용으로만 봐주세요.

//------------------------------------------------
//    Project Euler #31 - Coin Sums
//        - by Aubrey Choi
//        - created at 2015-02-04
//------------------------------------------------
#include <stdio.h>

int getcomb(int n, int d);

int main()
{
    printf("Ans = %d\n", getcomb(200, 0));
}

int getcomb(int n, int d)
{
    const int v[] = { 200, 100, 50, 20, 10, 5, 2, 1, 0 };

    if( n == 0 ) return 1;
    if( v[d] == 0 ) return 0;

    int sum = 0;
    int t = n/v[d];
    for( int i = 0 ; i <= t ; i++ )
        sum += getcomb(n-i*v[d], d+1);
    return sum;
}