백준 11726번: 2×N 타일링의 점화식

작은 직사각형부터 채워 봅니다

백준 11726번은 2×N 직사각형을 1×2, 2×1 타일로 채우는 경우의 수를 구하는 문제입니다. 답은 10007로 나눈 나머지로 출력합니다.

당시에는 작은 크기의 경우를 나열하고 규칙을 찾았습니다.

2×N 직사각형을 채우는 경우와 앞선 두 값의 관계를 정리한 그림

앞의 두 경우의 수를 더하면 다음 값이 됩니다. 마지막을 세로 타일 하나로 채우면 앞에는 2×(n-1)이 남고 가로 타일 두 개로 채우면 2×(n-2)가 남습니다.

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

처음 두 값을 dp[1] = 1, dp[2] = 2로 두고 3부터 점화식으로 값을 저장한 뒤 입력한 크기의 값을 꺼냅니다. 아래 코드는 n이 1이나 2일 때 바로 출력하고 나머지 경우에 배열을 만듭니다.

제출 코드

Java

import java.io.*;

class Main {

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

        int n = Integer.parseInt(br.readLine());

        if (n < 3) {
            bw.write(String.valueOf(n));
        } else {
            int[] dp = new int[n+1];

            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
                dp[i] = (dp[i-1]% 10007 + dp[i-2]% 10007) % 10007;
            }
            bw.write(String.valueOf(dp[n]));
        }
        bw.flush();
    }
}