Aizu Online Judge 0168 Kannondou

■0168 Kannondou

動的計画法．

dp[段数]=組み合わせ
dp[0]=1
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  void run(){  
17.   for(;;){  
18.    int n=sc.nextInt();  
19.    if(n==0){  
20.     break;  
21.    }  
22.    int[] dp=new int[n+4];  
23.    dp[0]=1;  
24.    for(int i=0; i<=n; i++){  
25.     dp[i+1]+=dp[i];  
26.     dp[i+2]+=dp[i];  
27.     dp[i+3]+=dp[i];  
28.    }  
29.    int ans=((dp[n]+9)/10+364)/365;  
30.    println(ans+"");  
31.   }  
32.  }  
33.   
34.  void debug(Object... os){  
35.   System.err.println(Arrays.deepToString(os));  
36.  }  
37.   
38.  void print(String s){  
39.   System.out.print(s);  
40.  }  
41.   
42.  void println(String s){  
43.   System.out.println(s);  
44.  }  
45.   
46.  public static void main(String[] args){  
47.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
48.   new Main().run();  
49.  }  
50. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   int[] dp=new int[n+4];
   dp[0]=1;
   for(int i=0; i<=n; i++){
    dp[i+1]+=dp[i];
    dp[i+2]+=dp[i];
    dp[i+3]+=dp[i];
   }
   int ans=((dp[n]+9)/10+364)/365;
   println(ans+"");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}