[JAVA] 백준 2193 이친수_DP

 

문제:

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

 

 

접근 : 

 

 - 1자리 수의 경우 = 1

 

 - 2자리 수의 경우 = 10

 

 - 3자리 수의 경우 = 100, 101

 

 - 4자리 수의 경우 = 1000, 1010, 1001

 

 - 5자리 수의 경우 = 10000, 10100, 10010, 10001, 10101

 

 - n자리 수의 경우 = n-1 자리 수의 경우 + 0, n-2 자리수의 경우 + 01

 

   -> DP[n] = DP[n-1] + DP[n-2]

 

 

코드 구현 :

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());

        if(n == 1){
            System.out.println(1);
            return;
        }

        long[] dp = new long[n+1];
        dp[1] = 1L;
        dp[2] = 1L;

        for(int i = 3 ; i <= n ; i++) dp[i] = dp[i-1] + dp[i-2];
        System.out.println(dp[n]);
    }
}