[백준] 1904. 01타일

문제 링크

[백준] 1904. 01타일

풀이 과정

동적 계획법 문제입니다.

00과 1을 사용할 수 있는 규칙에 따라 다음과 같이 N에 따라 만들어지는 수열을 만들어 볼 수 있습니다.

• N이 1일 때 : 1
• N이 2일 때 : 00, 11
• N이 3일 때 : 100, 001, 111
• N이 4일 때 : 0000, 1100, 1001, 0011, 1111

for (int i = 3; i <= N; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;

위와 같이 직접 만들어지는 수열을 작성해보며, 다음과 같은 규칙을 찾을 수 있습니다. 길이 i인 수열은 길이가 i-2인 수열에 00을 붙이거나, 길이 i-1인 수열에 1을 붙여 만들 수 있습니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N + 1];
        final int MOD = 15746;

        if (N <= 2) {
            System.out.println(N);
            return;
        }

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= N; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;

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