[Java] BOJ 11726 2×n 타일링

문제 

문제 링크 https://www.acmicpc.net/problem/11726

• 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
• 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 

  

• 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
• 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

아이디어

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

겪은 시행착오

• X

이제 쉬운 dp는 어느정도 풀 수 있게 된 것 같아 기쁘다! ㅎㅎ

코드

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

public class BOJ11726 {
    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일때 방법의 개수는 2이므로
        // 배열 1번째 값은 1, 배열 2번째 값은 2로 초기화
        sqr[1] = 1;

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

        // 3번째부터 n번까지 반복
        for(int i = 3; i <= n; i++){
            // 가로의 길이가 i일때 방법의 개수는
            // 가로의 길이 i - 1일때 방법의 개수와 i - 2일때 방법의 개수 합과
            // 같으므로 두 값을 더해준 뒤 10007로 나눈 나머지 값을 구함
            sqr[i] = (sqr[i - 1] + sqr[i - 2])%10007;
        }

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