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

문제

예제

풀이

이 문제도 앞서 쭉 푼 문제들과 비슷하다. 오히려 조건이 더 단순해서 쉽게 풀었다.

이친수의 조건은 다음과 같다.

• 0과 1만 사용 (이진수)
• 1이 연속되면 안된다.
• 0으로 시작하지 않는다.

dp[자리길이][마지막자릿값] 배열을 선언한다.

마지막 자릿값이 0이면 뒤에 0이나 1이 올 수 있다.(두 가지 경우의 수)
마지막 자릿값이 1이면 뒤에 0만 올 수 있다.(한 가지 경우의 수)

​

4자리와 5자리 이친수의 예를 들어보자

dp[4][0] = {1000, 1010}
dp[4][1] = {1001}

dp[5][0] = {10000, 10100, 10011}
dp[5][1] = {10001, 10101}

따라서 dp[n][0] = dp[n-1][0] + dp[n-1][1] 이고 dp[n][1] = dp[n-1][0] 이런 점화식이 도출된다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    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][1] = 1;

        //자릿수가 2일 때부터  ~ N일 때까지 탐색
        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]);
    }
}