[Java] 1904번: 01타일 Silver 3

문제 링크

이 문제도 껍데기만 다를 뿐 종이 붙이기와 똑같은 유형의 문제다.

이전에 썼던 네이버 블로그를 참고해도 되지만,

혹시나 내 블로그를 처음 찾아온 사람들을 위해 풀이를 남기겠다..!

풀이

DP 문제를 풀 때는 N이 어떻게 만들어지는지에 집중을 해야 한다.

그래서 규칙을 파악하기 위해 N = 4일 때 까지의 경우를 우선 적어봤다.

N = 3일 때도 마찬가지지만, 좀 더 눈에 띄는 N = 4 일 때를 보자.
N = 4인 경우는

1. N = 3일 때의 케이스에서 뒤에 1을 붙인 경우
2. N = 2일 때의 케이스에서 뒤에 00을 붙인 경우

이렇게 두 가지에 의해서 만들어지고 있다.

이건 N = 3일 때도 마찬가지이다.

N = 1일 때의 케이스인 1의 뒤에 00을 붙이고,
N = 2일 때의 케이스인 11 00의 뒤에 1을 붙이면
N = 3일 때의 케이스가 만들어진다.

즉, 그렇다는 말은 이러한 규칙이 계속 반복되면 N번째에서도 같은 일이 발생한다는 것이다.

그렇기에 우리는 점화식을 세울 수 있다.

X[N] = X[N-1] + X[N-2]

그리고 초기값 X[1] = 1, X[2] = 2를 설정해주고 구하려고 하는 N까지 반복하면 답을 구할 수 있다!

import java.io.*;
import java.util.*;

public class Main {
    private static int N;
    private static int[] dp;

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

        // N 입력 받기
        N = Integer.parseInt(br.readLine());

        // dp
        if (N == 1) {
            System.out.println(1);
        } else if (N == 2) {
            System.out.println(2);
        } else {
            dp = new int[N + 1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= N; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
            }

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