[백준] 2193번 이친수 JAVA DP

 

규칙 

• 1. 0으로 시작하지 않는다.
• 2. 1이 두 번 연속으로 나타나지 않는다.

풀이 방법

0다음에 올 수 있는 수는 0, 1

1다음에 올 수 있는 수는 0뿐

입력 N+1(보기 편하게 1을 더해서 표기) 배열을 2차원으로 선언해서

0으로 끝나는 수와 1로 끝나는 수를 계속 카운팅 해준다.

0로 끝나는 수는 [0][i-1] + [1][i-1]

1로 끝나는 수는 [0][i-1]로 입력된 수 만큼 계산하여

마지막에 둘의 합을 출력한다.

코드

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
//        규칙1. 첫자리에 0이 올 수 없다.
//        규칙2. 1이 두번 연속으로 나타날 수 없다.
        long[][] dp = new long[2][N+1];
        dp[1][1] = 1; //1로 끝나는 수의 개수. 
        dp[0][1] = 0; //0로 끝나는 수의 개수.

        for(int i=2; i<=N ; i++){
            //1다음에 올 수 있는건 0밖에 없다
            //0다음에 올 수 있는건 0, 1 두개다
            dp[1][i] += dp[0][i-1];
            dp[0][i] += dp[1][i-1] + dp[0][i-1];
        }
        System.out.println(dp[0][N] + dp[1][N]);
        reader.close();
    }
}