[Java] 11729 2xN 타일

문제

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

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



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

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

문제 풀이

전형적인 DP 문제이다.

초반에 조금 생각해보면 도형이 1개 놓여졌을 때부터 경우의 수를 생각해보면 세로로 타일을 놓는 경우 1개 밖에 없다.

다음으로 2개를 놓았을 때의 방법은 가로로 두개를 놓는 방법과 기존의 세로로 타일을 놓았던 경우에서 옆에 세로로 하나 더 두는 방법 총 2개가 나온다.

계속 진행해보자 3개의 타일을 놓을 수 있는 경우의 수는 2개를 놓는 경우에 수에서 옆에 세로타일을 놓는 방법과 

1개를 놓는 경우에 수에서 가로타일을 두개 놓는 방법이 있다.

슬슬 규칙이 보일거 같다. 혹시 모르니 한 단계 더 가보자 4개를 놓을 수 있는 경우의 수는 기존 3개를 놓는 경우의 수에서 옆에 세로 타일을 하나 두거나 2개를 놓는 경우의 수에서 가로 타일 두개를 놓는 방법이 있다.

여기까지 오면 느껴지는 게 있다. n개의 타일을 놓을 수 있는 경우의 수는 n-1개의 타일과, n-2개의 타일을 놓는 경우의 수를 합친 값이라는 것. 즉 dp[n] = dp[n-1] + dp[d-2] 이다. 이제 점화식을 찾았으니 해당 점화식으로 문제를 풀어나가면 된다.

단, 여기서 중요한 점은 1 ~ N까지의 타일 놓는 경우의 수를 계산할 때 마다 10007을 나눠주어야한다. 마지막에만 해줄 경우 그 범위가 Integer.Max_Value를 넘길 수가 있다.

자바 코드

import java.util.Scanner;

public class Tiling2n {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

        System.out.println(dp[n]);

    }
}