[BJ ] 1904 : 01타일

       문제 요약        

- 문제

00 또는 1 로 이뤄진 타일

 

 

- 입출력

 

 

         아이디어        

dp[i] = dp[i-2] + dp[i-1]

dp[1] = 1

dp[2] = 2

 

 

         소스코드        

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
	// 마지막 dp[i] -> 그전 dp[i-2]0 또는 dp[i-1]1
	  static int dp[];
	    static int cal(int N){
	        if(dp[N] == -1)
	            dp[N]=(cal(N-1)+cal(N-2))%15746;
	        return dp[N];
	    }
	    public static void main(String[] args) throws Exception {
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        int N = Integer.parseInt(br.readLine());
	        dp = new int[1000001];
	        Arrays.fill(dp,-1);
	        dp[0] = 0;
            dp[1] = 1;
	        dp[2] = 2;
	        
	        System.out.println(cal(N));
	    }
}