[백준] 2xN 타일링 - 11726

링크

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

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

풀이

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

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

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

즉, f(k)가 2xk 크기의 직사각형을 채우는 방법의 수를 반환하는 함수일 때
f(k) = f(k-1) + f(k-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[n] = rect[n-1] + rect[n-2]
         * 0과 1은 기본으로 두고, 2부터 채우기 시작. 패턴은 아래와 같다.
         * 1. n-1 모양 앞에 |를 더한다.
         * 2. n-2 모양 앞에 =를 더한다.
         * 
         * 1: |
         * 2: ||, =                     ->      |+|, =+0 
         * 3: |||, |=, =|               ->      |+||, |+=, =+|
         * 4: ||||, ||=, |=|, =||, ==   ->      |+|||, |+|=, |+=|, =+||, =+=
         */
        int[] rect = new int[n+1];
        rect[0] = rect[1] = 1;
        
        // solve | 10007으로 나눈 나머지를 배열에 저장.
        // (A+B)%C == (A%C + B%C)%C 
        for(int i=2; i<=n; i++){
            rect[i] = (rect[i-1]%10007 + rect[i-2]%10007)%10007;
        }

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