DP - 백준2193 이친수

풀이 -> 아래 코드 주석

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //문제
        //1. 1로 시작
        //2. 1이 연속으로 나오지 않음
        //점화식
        //n+1번째 이진수 구하기
        //n+1 = if(n이 1로 끝나면) n+0    ex)1 -> 10
        //n+1 = if(n이 0으로 끝나면) n+0, n+1    ex)0 -> 00, 01
        //n[1] = 1
        //n[2] = 10
        //n[3] = 100 101
        //n[4] = 1000 1001 1010
        //이렇게 직접 단계를 그려보면 어떤식으로 늘어나는지 보임, 그것이 아래 점화식
        //n의 끝이 0인 숫자갯수 = (n-1)의 끝이 0인 숫자갯수 + (n-1)의 끝이 1인 숫자갯수
        //n의 끝이 1인 숫자갯수 = (n-1)의 끝이 0인 숫자갯수
        //테이블
        long[][] dp = new long[91][2];
        //초기화
        dp[1][0] = 0;    //0갯수
        dp[1][1] = 1;    //1갯수
        //채우기
        for(int i = 2; i <= 90; i++){
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }
        //n의 끝이 0인 숫자갯수 + n의 끝이 1인 숫자갯수 의 합
        System.out.println(dp[n][0] + dp[n][1]);	
    }
}

나름 고민을 해서 풀었는데 아이디어가 떠올랐다. 다른 사람들의 풀이도 똑같았다.
알고리즘을 풀다보니 머리가 좋아지는 것 같다..ㅋㅋ

+한 가지 어이없는 게, 처음에 답이 틀렸다고 떴는데 그 이유가 테스트케이스에서 값의 크기 때문에 int배열대신 long배열을 써야 했다.
무슨 이친수를 직접 저장하는 것도 아니고, 그 갯수만 저장하는데 그게 Integer크기가 넘어가는지 나보고 어떻게 알라는 거?