[백준] 온라인 저지 2193번 : 이친수 구하기(Java), DP

 

0으로 끝나는 이친수와 1로 끝나는 이친수로 구분해서 생각해보자.

 

D[i][0] : i 길이에서 0으로 끝나는 이친수 개수

D[i][1] : i 길이에서 1로 끝나는 이친수 개수

 

다음과 같은 점화식을 세울 수 있다.

> 0은 이전 단계의 0과 1로 끝나는 모든 경우의 수에 붙일 수 있으므로 D[i][0] = D[i-1][0] + D[i-1][1]

> 1은 이전 단계의 0으로 끝나는 수에만 붙일 수 있으므로 D[i][1] = D[i-1][0]

 

 

 

문제 풀이

import java.util.Scanner;

public class P2193_이친수구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        long dp[][] = new long[N+1][2];

        dp[1][0] = 0;
        dp[1][1] = 1;

        for(int i=2; i<=N; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }

        System.out.println(dp[N][0] + dp[N][1]);
    }
}