AOJ 0168 - Kannondou

AOJ dp pck

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168

解法 :

一つ前の状態を考える。
i段目にいるためには
i-1段目から1段,
i-2段目から2段,
i-3段目から3段
登る場合のみである。

トリボナッチ数を作る
dp_i=dp_{i-1}+dp_{i-2}+dp_{i-3}

#include<iostream>

using namespace std;

int dp[35];

int main(){
	dp[0]=1;
	dp[1]=1;
	dp[2]=2;
	for(int i=3;i<31;i++){
		dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
	}
	
	int n;
	while(cin>>n && n){
		cout<<dp[n]/3650+(dp[n]%3650!=0)<<endl;
	}
}