11726 2xn 타일링 JAVA

 

 

https://www.acmicpc.net/problem/11726

 

내가 처음 DP를 접할 때, 좋은 접근 방법 중 하나가 큰 문제와 가장 작은 문제로 구분하는 것이였다.

이 문제 또한 큰 문제와 작은 문제로 나눌 수 있는데, 가장 작은 문제는 맨 뒷 블럭에 올수 있는 형태로 구분하였다.

 

이 문제의 경우엔 총 2가지인데, 1*2 타일을 높이로 두개 쌓거나, 2*1 타일을 하나 두는 것이다.

 

1 * 2 타일의 세로로 두개를 올린 경우 가로의 길이는 (n-2)가 되고, 2 * 1 타일의 경우엔 가로의 길이는 (n-1)이 된다.

 

따라서 아래와 같이 점화식을 작성하면, 타일의 갯수를 구해낼 수 있다.

D[n] = f(n-1) + f(n-2);

 

import java.io.*;

public class D11726 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        D = new int[n+1];
        System.out.println(go(n));
    }
    private static int[] D;
    private static int go(int n) {
        if(n < 3)
             return n;

        else if(D[n] > 0) return D[n];

        D[n] = go(n-1) + go(n-2);
        return D[n] % 10007;
    }
}

 

단 주의해야 할 점은, 10007로 나눈 나머지로 타일의 갯수를 구해야 하는 것이다.

애초에 약 200? 정도만 되도, 나머지로 하지 않으면 오버 플로우가 발생해서 이상한 값이 되었었다.

필자는 문제를 제대로 안봐서 틀리고 나서야 나머지를 확인하였다 ㅠㅠ