「漸化式を立てる」という発想があるだけで勝ち。
1, 2, 3段までは初期値として手で数え、それ以降は-1, -2, -3段の場合の数の足しあわせとして漸化的に計算する。
ちなみに初期の3段目を間違えて3通りだと思って、サンプルが通らなかったので、なるべく自動に任せた方が良いなと教訓を得ました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #include <iostream>using namespace std; int main(void){ int n; long long a[30] = {1, 2, 4}; for (int i = 3; i < 30; i++) a[i] = a[i - 1] + a[i - 2] + a[i - 3]; while (cin >> n && n) cout << 1 + a[n-1] / 3650 << endl; return 0;} |
1, 2, 3段の数え間違いを避けたいなら、負の段の場合の数を0, 0段目を1, 1段目を0として、番兵法とかを使うと良いかもしれない。