[Java] BOJ 11727 2×n 타일링 2

문제 

문제 링크 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로 나눈 나머지를 출력한다.

아이디어

• 직사각형을 채우는 방법의 수를 저장할 n + 1 크기의 배열을 생성한다.
• 직사각형의 가로가 1일때 방법의 수는 1, 가로가 2일때 방법의 수는 3이기 때문에 배열의 첫번째 값은 1, 두번째 값은 3으로 초기화한다.
• 3부터 n까지 반복을 하는데, 가로가 i인 직사각형을 채울 방법의 수는 가로가 i - 1인 직사각형을 채우는 방법의 수와 가로가 i - 2인 직사각형을 채우는 방법의 수를 2배한 값을 더한 값과 같으므로 해당 두 값을 더하고 10007을 나눠 나머지 값을 배열의 i번째에 저장한다.

겪은 시행착오

• X

2×n 타일링이랑 문제가 거의 비슷해서 쉽게 풀었다..!

코드

import java.util.*;
import java.io.*;

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

        // 직사각형 가로 길이
        int n = Integer.parseInt(br.readLine());

        // 직사각형을 채우는 방법의 수를 저장할 배열
        int sqr[] = new int[n + 1];

        // 직사각형의 가로 길이가 1일 때, 채우는 방법의 개수가 1이고
        // 가로 길이가 2일 때, 채우는 방법의 개수가 3이므로
        // 배열의 1번째 값을 1로, 2번째 값을 3으로 초기화
        sqr[1] = 1;

        if(n > 1){
            sqr[2] = 3;
        }

        // 3부터 n까지 반복
        for(int i = 3; i <= n; i++){
            // 가로가 i인 직사각형을 채우는 방법의 수는
            // 가로가 i - 1인 직사각형을 채우는 방법의 수와
            // 가로가 i - 2인 직사각형을 채우는 방법의 수에 2를 곱한 값을 더한 값과
            // 같기 때문에 두 값을 더해준 뒤 10007로 나눈 나머지 값을 구함
            sqr[i] = (sqr[i - 1] + 2*sqr[i - 2]) % 10007;
        }

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