川のブログ

川の適当気ままなブログです。 

AOJ 0168 Kannondou

こんにちは川です。

今回はdpですね。

n段目の通り数=n-3段目の通り数+n-2段目の通り数+n-1段目の通り数

みたいな感じですね。

 

ソースコード

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int n;
 int dp[31]={};
 dp[0]=1;dp[1]=1;dp[2]=2;
 for(int i=3;i<31;i++){
  for(int j=1;j<4;j++){
  dp[i]+=dp[i-j];
  }
 }
 while(cin>>n,n){
  int num=dp[n]/3650;
  if(dp[n]%3650!=0)num++;
  cout<<num<<endl;
 }
}