[백준] 11726번 : 2xn 타일링

문제

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

입력

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

출력

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

문제해결방법

1x2 타일을 두 개 붙여서 두 칸을 채우는 타일을 만든다.

이렇게 하면 1칸 짜리 타일 1개, 2칸 짜리 타일 1개로 생각할 수 있다.

n번째 타일을 채우는 경우의 수를 생각하면 n-1 번째 타일에서 1칸 짜리 타일을 붙이는 방법과

n-2 번째 타일에서 2칸 짜리 타일을 붙이는 방법이 있다.

이것을 수식으로 나타내면 다음과 같다.

타일[n] = 타일[n-1] + 타일[n-2]

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main11726_2Xn타일링 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        arr[0] = 1;
        arr[1] = 1;
        for(int i=2; i<=n; i++) arr[i] = (arr[i-1] + arr[i-2])%10007;
        System.out.println(arr[n]);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.