백준 11726번 (2×n 타일링)

오늘은 백준 11726번 문제를 풀어봤다.
문제는 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 것이다.
그리고 최종 결과를 10007로 나눈 나머지를 출력해야 한다.

문제 접근

처음에는 직접 경우의 수를 세어보려고 했는데, n이 커지면 경우의 수가 기하급수적으로 늘어난다.
그래서 Dynamic Programming(DP) 으로 접근해야 한다.

dp[n] = 2×n 크기를 채우는 경우의 수

마지막에 놓인 타일을 기준으로 생각하면,

세로 타일(2×1) 하나를 오른쪽 끝에 놓는 경우 → dp[n-1]

가로 타일(1×2) 두 개를 오른쪽 끝에 놓는 경우 → dp[n-2]

따라서 점화식은
dp[n] = dp[n-1] + dp[n-2]

기저 조건

dp[1] = 1 → 세로 타일 하나로 채우는 방법

dp[2] = 2 → (세로 두 개) 또는 (가로 두 개)

MOD = 10007 이란?

문제에서 "결과를 10007로 나눈 나머지를 출력"하라고 한다.
이유는 경우의 수가 너무 커지기 때문이다.
예를 들어 n=1000이면 수가 엄청 커져서 오버플로우가 날 수도 있다.

그래서 매 연산마다 % 10007을 해주면:

값이 커지지 않는다.

문제 조건을 만족한다.

그리고 10007은 변하지 않는 값이므로 이렇게 상수로 선언한다:

const int MOD = 10007;

작성코드

using System;

class ㅠㅁ차ㅓㅐㅐㅜ
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine()!);
        const int MOD = 10007;

        if (n == 1) { Console.WriteLine(1); return; }
        if (n == 2) { Console.WriteLine(2); return; }

        int[] 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]) % MOD;
        }

        Console.WriteLine(dp[n]);
    }
}

오늘 배운 점

2×n 타일링 문제는 피보나치랑 비슷한 DP 점화식으로 풀린다.

dp[n] = dp[n-1] + dp[n-2]

결과값을 10007로 나눈 나머지를 출력해야 하므로 const int MOD = 10007; 을 선언하고 매번 % MOD를 적용한다.

이렇게 하면 큰 수를 다룰 때 오버플로우도 막을 수 있고, 문제에서 요구하는 정답 형식도 만족시킬 수 있다.