Project Euler 31

http://projecteuler.net/index.php?section=problems&id=31

再帰で簡単にかけるので、メタプログラミングしてみた。

#include <iostream>

const int coins[] = { 1, 2, 5, 10, 20, 50, 100, 200 };
const int   num_coins = sizeof(coins) / sizeof(int);

template<int N, int M> struct num_divs;

template<int N, int M, bool B>
struct sum_divs {
    static const int coin = coins[M];
    static const int value = num_divs<N - coin, M>::value
                    + sum_divs<N - coin, M, N >= coin>::value;
};

template<int N, int M>
struct sum_divs<N, M, false> {
    static const int value = 0;
};

template<int N, int M>
struct num_divs {
    static const int value = num_divs<N, M-1>::value
                            + sum_divs<N, M, N >= 0>::value;
};

template<int M>
struct num_divs<0, M> {
    static const int value = 1;
};

template<int N>
struct num_divs<N, -1> {
    static const int value = 0;
};


int num_divs(int n, int max_coin = num_coins - 1) {
    if(n == 0)
        return 1;
    else if(max_coin < 0)
        return 0;
    
    int counter = 0;
    for(int i = 0; i <= max_coin; i++) {
        int coin = coins[i];
        for(int j = 1; j * coin <= n; j++)
            counter += num_divs(n - coin * j, i - 1);
    }
    return counter;
}

int main() {
    std::cout << num_divs(200) << std::endl;
}