알고리즘 - 백준, 2193번 이친수 (DP)

비교적 쉬웠던 문제 중 하나다.
피보나치수열과 문제의 점화식 도출과정이 같아 금방 풀 수 있었다.

✅점화식 도출

먼저, n=1인 경우
0으로 시작하는 이친수가 없기 때문에 1로 시작하는 이친수가 유일하다. 따라서 d[1] = 1

n=2인 경우
1로 시작하는 이친수는 없기 때문에 10 하나만 가능하다. 따라서 d[2] = 1

n=3인 경우
1로 시작하는 이친수는 10 하나밖에 없으므로, 00과 11이 가능하다. 따라서 d[3] = 2다.

n=4인 경우
10으로 시작하는 이친수는 001과 100이 가능하다.
00으로 시작하는 이친수는 000과 001이 가능하고,
11로 시작하는 이친수는 110 하나밖에 없다.
따라서 d[4] = 3

이를 통해 점화식이 다음과 같다는 것을 알 수 있다.
n이 1일 때와 2일 때는 d[n] = 1이고,
n이 3 이상일 때는 d[n] = d[n-1] + d[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());

        long[] dp = new long[n + 1];
        dp[1] = 1;
        if (n >= 2) {
            dp[2] = 1;
        }

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

        System.out.println(dp[n]);
    }
}