[백준]2193_이친수

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



점화식 d[n] = d[n-1] + d[n-2]





import java.util.Scanner;

public class P2193 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        //long 8 byte
        //점화식
        //d[n] = d[n-1] + d[n-2]
        
        //d[n][l] : n자리 이친수, 마지막자리 l
        //0으로 끝나는 경우 d[n][0] = d[n-1][0] + d[n-1][1] 
        //1으로 끝나는 경우 d[n][1] = d[n-1][0] //0만 가능
        
        //정답은 0으로 끝나는 경우 또는 1로 끝나는 경우
        //d[n][0] + d[n][1] 
        int[] d = new int[n]; 
        
        d[0] = 0;
        if(n >= 1) {
            d[1] = 1;
        }
        for (int i = 2; i < n; i++) {            
            d[i] = d[i-1] + d[i-2];  
        }
        System.out.println(d[n]);
    }
}