11727 - 2 x n 타일링2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	44267	26509	21036	59.311%

2 x n 직사각형을 1 x 2, 2 x 1, 2 x 2 타일로 채우는 경우의 수를 구하는 문제이다.

 

이렇게 여러가지 방법으로 경우의 수를 구할 때는 점화식을 이용해서 푸는게 일반적이다.

 

각 n에대해 2 x n 크기의 직사각형을 채우는 방법의 수가 들어있는 배열을 d라고하자.

 

d[N]에대한 점화식을 구하기 위해 아래와 같은 과정이 필요하다.

 

d[N - 1]의 값을 임의로 구했다고 했을 때, d[N - 1]을 구한 후에는 한 줄이 남으므로 1 . 2 x 1 타일 1개로 한 줄을 채우는 경우 한 가지이고,

 

d[N - 2]의 값을 구했다고 하면 d[N - 2]를 구한 후에는 두 줄이 남으므로 1 . 2 x 1 타일 2개로 두 줄을 채우는 경우 2 . 1 x 2 타일 2개로 두 줄을 채우는 경우 총 두가지가 있다.

 

따라서 d[N] = d[N - 1] + d[N - 2]라는 점화식을 세울 수 있게 된다. 따라서 d[N]을 구한 후, 문제에서 원하는것은 10007로 나눈 나머지를 출력해야하기 때문에 각 값을 계산 할 때 마다 10007로 나눈 나머지로 값을 나누어주었다. 마지막에 10007로 값을 구하게 된다면, N = 1000일 때 값이 int 범위를 벗어난 경우가 되므로 N = 1000일 때의 값을 모두 구한 후 10007로 나눈 나머지를 출력하게 된다면 올바르지 않은 값을 출력하게 된다. 지속해서 나머지가 필요하다면, 미리 나머지를 구해놓아도 이후에 구한 나머지와 같으므로 미리 나머지를 구해 저장하는 방식으로 구현했다.

 

package backjoon;
import java.util.Scanner;

public class Two_multiple_n_Tiling_2 {
    static int d[] = new int[1001];
    public static int solve(int N){
        if (N == 1) return (1);
        else if (N == 2) return (3);
        else if (d[N] > 0) return d[N];
        else {
            d[N] = (solve(N - 1) + solve(N - 2) * 2) % 10007;
            return d[N];
        }
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        System.out.println(solve(N));
    }
}