[알고스팟] ASYMTILING (비대칭 타일링)

문제 정보

시간 제한 : 1000ms
메모리 제한 : 65536kb

그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 좌우 대칭이어서는 안 됩니다. 위 그림은 2 * 5 크기의 직사각형을 채우는 비대칭 타일링 방법 6가지를 보여줍니다. 다음의 2가지는 좌우대칭이기 때문에 세지 않습니다.

n 이 주어질 때 가능한 비대칭 타일링 방법의 수를 계산하는 프로그램을 작성하세요. 방법의 수는 매우 클 수 있으므로, 1,000,000,007 로 나눈 나머지를 출력합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 그 후 각 줄에 사각형의 너비 n (1 <= n <= 100) 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지를 출력합니다.

예제 입력

3
2
4
92

예제 출력

0
2
913227494

내가 푼 답안

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Asymtiling {

    public static int N;
    public static long cache[];

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub

        System.setIn(new FileInputStream("C://eclipse-workspace/sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine().trim());
        for(int testCase=1; testCase<=T; testCase++) {
            N = Integer.parseInt(br.readLine().trim());
            cache = new long[N+1];

            for(int i=0; i<cache.length; i++) {
                cache[i] = -1;
            }

            long result = tiling(N);
            long dup = tiling((N/2)+1);

            bw.flush();

            // 1000000007 로 나눈 나머지를 빼면 음수가 나올 수 있으므로 MOD를 더했다가 나누는 기법을 사용한다.
            // 예를들어 MOD+1 만큼의 경우의수 - 100 만큼의 경우의수를 하면 모듈라연산에의해 -99가 나온다.
            // MOD+1-100 이므로 -99에 MOD를 더하면 제대로 된 경우의 수가 나온다. 초과될 수 있으므로 다시 MOD로 나눈다.
            bw.write((result-dup+1000000007)%1000000007 + "\n");
        }
        bw.close();
    }

    public static long tiling(int n) {

        if(n <= 1) {
            return 1;
        }

        if(cache[n] != -1) {
            return cache[n];
        }

        cache[n] = (tiling(n-1) + tiling(n-2))%1000000007;

        return cache[n];

    }

}

회고

모듈라 연산에 대해서 더 자세히 알아야겠다.
문제 접근도 괜찮았고 빨리 풀 수 있었다.
다만 MOD로 나눈뒤 음수가 나올 수 있다는 점을 간과했다. 하나 더 배웠다.