[백준] 2193 이친수 - Dynamic Programming / Java

• 문제 링크

2193번: 이친수

 

• 풀이 과정

[백준] 10844 쉬운 계단 수 - Dynamic Programming / Java

위 문제와 유사하게 2차원 dp 배열로 접근하여 풀이한다.

 

이친수는 0으로 시작하지 않는 조건에 의하여 dp[1][0] = 0, dp[1][1] = 1 으로 초기화하고,

 

1이 두 번 연속으로 나타나지 않는 조건에 의하여

자릿값이 0 일 시 이전 자릿수의 값은 0, 1 모두 가능하고,(dp[i][0] = dp[i - 1][0] + dp[i - 1][1])

자릿값이 1 일 시 이전 자릿수의 값은 0만 가능하다.(dp[i][1] = dp[i - 1][0])

이 후 n 자리의 이친수의 개수 dp[n][0] + dp[n][1] 을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        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];
        }

        bw.write(dp[n][0] + dp[n][1] + "\n");
        bw.flush();
    }

}