[백준] 2xN 타일링2 - 11727

링크

https://www.acmicpc.net/problem/11727

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

11726번과 유사하다.

패턴을 파악해 DP를 사용했다.
2x1 크기의 직사각형을 채우는 방법은, 2x1타일 1개를 사용해 채우는 1가지 방법이 있다.
2x2 크기의 직사각형을 채우는 방법은, 2x1타일 2개 또는 1x2타일 2개
또는 2x2타일 1개를 사용하는 3가지 방법이 있다.

2x3 크기의 직사각형을 채우는 방법은, |||, |=, |ㅁ, =|, ㅁ| 5가지 방법이 있다.
2x4 크기의 직사각형을 채우는 방법은, ||||, ||=, ||ㅁ, |=|, |ㅁ|, =||, ==, =ㅁ, ㅁ||, ㅁ=, ㅁㅁ 11가지 방법이 있다.

이를 패턴화 하면 직사각형을 채우는 방법은 아래와 같다.

즉, f(k)가 2xk 크기의 직사각형을 채우는 방법의 수를 반환하는 함수일 때
f(k) = f(k-1) + f(k-2)*2 가 성립한다.

10007로 나눈 나머지를 출력하므로, 나머지 연산의 분배법칙을 사용한다.

코드

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

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

        // input | n->int
        int n = Integer.parseInt(br.readLine());

        /** init | rect[] -> int[]
         * rect[x] = rect[x-1] + rect[x-2] * 2
         * rect배열의 0과 1을 채우고, 2부터 패턴에 따라 값을 채움. 패턴은 아래와 같음
         * 0: 0
         * 1: |
         * 2: ||, =, ㅁ                     -> |+|, =+0, ㅁ+0
         * 3: |||, |=, |ㅁ, =|, ㅁ|         -> |+||, |+=, |+ㅁ, =+|, ㅁ+|
         * 4: ||||, ||=, ||ㅁ, |=|, |ㅁ|, =||, ==, =ㅁ, ㅁ||, ㅁ=, ㅁㅁ
         *     -> |+|||, |+|=, |+|ㅁ, |=|, |+ㅁ|, =+||, =+=, =+ㅁ, ㅁ+||, ㅁ+=, ㅁ+ㅁ
         */
        int[] rect = new int[n+1];
        rect[0] = rect[1] = 1;

        // solve | (A+B)%C == (A%C + B%C) % C
        for(int i=2; i<=n; i++){
            rect[i] = (rect[i-1]%10007 + (rect[i-2]*2)%10007) % 10007;
        }

        // print
        System.out.println(rect[n]);
    }
}