[BOJ11726] 2×n 타일링

[문제 링크]
https://www.acmicpc.net/problem/11726

풀이

1. 접근 방법

이 문제는 2xN 크기의 직사각형을 1x2와 2x1 타일로 채우는 경우의 수를 구하는 전형적인 동적 계획법(Dynamic Programming) 문제이다. 문제의 규칙성을 파악하여 점화식을 세우는 것이 핵심이다.

2. 사고 흐름

N의 크기에 따른 경우의 수를 직접 나열해보며 규칙을 찾는다.

• N=1: 2x1 사각형은 2x1 타일 하나로 채울 수 있다. (1가지)
• N=2: 2x2 사각형은 2x1 타일 두 개를 세로로 놓거나, 1x2 타일 두 개를 가로로 놓을 수 있다. (2가지)
• N=3: 2x3 사각형을 채우는 방법은, 2x2 사각형을 채우는 방법에 2x1 타일을 오른쪽에 추가하는 방법과, 2x1 사각형을 채우는 방법에 1x2 타일 두 개를 오른쪽에 추가하는 방법의 합이다. 즉, dp[2] + dp[1] = 2 + 1 = 3가지이다.

여기서 dp[n] = dp[n-1] + dp[n-2] 라는 점화식을 유추할 수 있다. 이는 피보나치 수열과 동일한 형태를 띤다. 단, 문제에서 요구하는 것은 결과를 10,007로 나눈 나머지이다.

3. 동작 방식

1. N의 크기를 입력받는다.
2. 크기가 N+1인 dp 배열을 생성한다.
3. 점화식의 기저 사례(base case)인 dp[1] = 1과 dp[2] = 2를 초기화한다.
4. 반복문을 통해 i=3부터 N까지 점화식 dp[i] = (dp[i-1] + dp[i-2]) % 10007을 수행하여 dp 배열을 채운다.
5. 최종 결과인 dp[N]을 출력한다.

4. 코드

//BOJ11726 2xn 타일링
//https://www.acmicpc.net/problem/11726
package BOJ11726;

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

public class Main {
    static int[] dp;
    /*
    * f(1) = | -> 1
    * f(2) = ||, = ->2
    * f(3) => |=, =|, ||| -> 3
    * f(4) => ||||, ==, |=|, =||,||= -> 5
    * f(n) => f(n-1) + f(n-2)
    * */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader([System.in](http://System.in)));
        int N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        dp[1] = 1;
        if (N >= 2) {
            dp[2] = 2;
        }
        for (int i = 3; i <= N; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2])%10_007;
        }
        System.out.println(dp[N]);
    }
}