문제

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

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

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

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

풀이

타일은 1x2, 2x1로 두 종류이다.
현재 단계에서 어떤 타일을 사용하는지로 나눠 점화식을 세울 수 있다.
1) 1x2을 사용하는 경우
현재 단계가 i인 경우 i번째 칸과 (i-1)번째 칸을 1x2 타일 2개를 이용해서 채우게 된다.
따라서 dp[i-2] 가지의 경우의 수가 있다. (1x2로 새로운 칸을 채우는 경우는 한가지밖에 없다.)
2) 2x1을 사용하는 경우
현재 단계가 i인 경우 i번째 칸을 2x1 타일 1개를 이용해서 채우게 된다.
따라서 dp[i-1] 가지의 경우의 수가 있다. (마찬가지로 새로운 칸을 채우는 경우는 한가지)
=> $dp[i] = dp[i-2]+dp[i-1]$

🚫주의할 점
dp를 초기화할 때 dp[0]과 dp[1]을 각각 1과 2로 초기화 해주어야 하는데 n=1인 경우를 고려하여 작성해야 한다. (아니면 n=1일 때 ArrayIndexOutOfBounds 런타임에러 발생)

코드

import java.io.*;
import java.util.*;
public class Main {
    static int[]dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        dp=new int[n];

        dp[0]=1;
        if(n>1) dp[1]=2; 
        for(int i=2;i<n;i++){
            dp[i]=(dp[i-2]+dp[i-1])%10007;
        }

        System.out.println(dp[n-1]);
    }

}