[java] 11727 2×n 타일링2

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

 

 

package backjoon_11727;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub\
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(result(n));
 
    }
    
    public static int result(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        
        if(n>1) {
            dp[2] = 3;
        }
        
        for(int i = 3; i<=n; i++) {
            dp[i] = (dp[i-1] + 2*dp[i-2])%10007;
        }
        
        return dp[n];
    }
 
}

 

1을 입력하면 한가지 경우밖에 없기 때문에 1로 지정하고, 2를 입력하면 3가지 방법밖에 없기 때문에 3으로 고정시켜둔다.

이 문제는 전과 비슷하지만 다르다. 2x2 2x1 1x2를 사용하기 때문에 생각하는데 좀 걸렸다.

dp[i-1] 는 2x(i-1) 크기 직사각형 타일을 채우기 위해 사용한다. 만약 2x1 타일을 세로로 추가하면 2xi 직사각형이 만들어진다. 그래서 dp[i-1]을 사용한다. 2*dp[i-2] 는 1x2 타일 두 개를 넣는 경우를 계산한다. 그리고 2x2 타일을 놓아도 같은 결과가 만들어지기 때문에 2를 곱한다.