DP :: 백준 :: 이친수 :: 2193

이친수 2193

https://www.acmicpc.net/problem/2193

[문제 풀이]

자리수 : n

dp[i][0] : i자리 이친수 중 0으로 끝나는 이친수의 개수

dp[i][1] : i자리 이친수 중 1로 끝나는 이친수의 개수

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

dp[i][1] = dp[i-1][0]

답 : dp[n][0]+dp[n][1]

import java.io.BufferedReader;
import java.io.InputStreamReader;
 /*
  * 2193번 이친수
  */
public class Main{
    static long d[][];
    static int n;
      
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine());
        d = new long[n+1][2];
        d[1][0] = 0;
        d[1][1] = 1;
        for(int i = 2; i <= n; i++){
            d[i][0] = d[i-1][0]+d[i-1][1];
            d[i][1] = d[i-1][0];
        }
         
        System.out.println(d[n][0]+d[n][1]);
    }
}