[백준] 11726. 2 x N 타일링

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

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

입력

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

출력

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

---

예제 입력 2

9

예제 출력 2

55

---

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if(n == 1) {
            System.out.println(1);
        }
        else if(n == 2) {
            System.out.println(2);
        }
        else {
            int[] arr = new int[n + 1];
            arr[1] = 1;
            arr[2] = 2;
            for(int i = 3; i <= n; i++) {
                arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
            }
            System.out.println(arr[n]);
        }
    }
}

---

DP 배열을 이용하여 값을 저장한다.

2 x 1을 만들때는 1개

2 x 2를 만들때는 2개

2 x 3을 만들때는 2 x 1짜리 + 2 x 2짜리

2 x N은 2 x (N-1)짜리 + 2 x (N-2)짜리

 

로 계산하였다.