問題はこちら

解答

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define MAX 1000000

vector<int> dp1(MAX + 1, MAX);
vector<int> dp2(MAX + 1, MAX);

int main() {
    int n;
    dp1[0] = 0;
    dp2[0] = 0; // <- 奇数の

    for (int i = 1;; i++) {
        int t = i * (i + 1) * (i + 2) / 6;
        if (t > MAX) break;

        for (int j = 1; j <= MAX; j++) {
            if (j >= t) {
                dp1[j] = min(dp1[j], dp1[j - t] + 1);
            }
        }

        // vv 奇数の
        if (t % 2 == 1) {
            for (int j = 1; j <= MAX; j++) {
                if (j >= t) {
                    dp2[j] = min(dp2[j], dp2[j - t] + 1);
                }
            }
        }
    }

    while (cin >> n, n) {
        cout << dp1[n] << " " << dp2[n] << endl;
    }

    return 0;
}

解説

動的計画法(Dinamic Programming)の問題.

$dp[N]$を $dp[N]=$正四面体数の個数の和 で定義する。 このとき、漸化式は, $t$を正四面体数とすると、 $dp[N] = min \left( dp[N], dp[N-t]+1 \right)$ のようになる。


これでAC.

DPについてはこのスライドを読むと良い。