DP [백준 2193번 이친수] -java-

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

2193번: 이친수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(br.readLine());
        
        int[] dp = new int[length+1]; //편의를 위하여 배열의 길이를 이진수 길이보다 1 크게 만든다.
                                      //-> 10번째 숫자이면 dp[9]를 접근하는게 맞으나 dp[0]을 버림으로써 인덱스 넘버가 곧 순서가 되게끔 하기 위하여 
        dp[0]=0;
        dp[1]=1;
        
        for(int i=2;i<=length;i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        System.out.println(dp[length]);
 
    }
 
}

dp배열은 n자리 이친수를 나타낸다.

n번째에 0이 들어간 이친수의 갯수는 n-1번째에 1혹은 0모두 들어갈 수 있다.  그러므로 dp[n-1]과 값이 같다.

그러나 n번째에 1이 들어가게 되면 n-1번째에는 반드시 0이 들어가야하고, n-2번째에 1 혹은 0이 모두 들어갈 수 있어 dp[n-2]와 같게 된다. 

그리하여 dp[n]=dp[n-1]+dp[n-2]로 해결할 수 있게 된다.