DP - 백준11726 2xn 타일링

첫번째 시도
아무리 생각해봐도 감도 안와서 (바킹독 선생님 조언대로) 직접 테이블을 한 번 채워봤다.

이렇게 그려놓고 다시 가만 생각해보니, 일단 홀수번째의 갯수는 이전 짝수번째의 갯수 +1 이라는 것을 알았다. 그래서 일단 dp[홀수] = dp[n-1] +1 까지는 생각했다.
그렇다면 짝수는 어떻게 구할 것인가를 생각해봤는데, 이건 아무리봐도 내 지능으로 당장 해결할 수 없을 것 같았다.

해답
역시 바킹독 선생님도 말씀하시길 처음 보면 감을 못 잡는게 당연하다고 하셨다.
풀이방법도 진짜 신박했다.
2xn개의 칸이 주어졌을 때 2가지로 나누어 생각하는 것이다.
1. 첫번째 칸에 세로블럭이 들어가는 경우
2. 첫번째 칸에 가로블럭이 들어가는 경우
1번의 경우에는 당연히 1칸이 사라져 2x(n-1)칸을 채우는 갯수와 같다.
2번의 경우에는 해당 칸에도 가로블럭이 들어갈 수 밖에 없으므로 2칸이 사라져 2x(n-2)칸을 채우는 갯수와 같다.
따라서 1번의 경우의 수와 2번의 경우의 수를 합치면 2xn개의 칸을 채우는 갯수가 나온다.
이는 곧 점화식으로 dp[n] = dp[n-1] + dp[n-2]와 같다.

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //점화식
        //첫번째 타일을 세로로 깔은 경우 : dp[n-1]
        //첫번째 타일을 가로로 깔은 경우 : dp[n-2]
        //dp[n] = dp[n-1] + dp[n-2]
        //초기값 설정
        int[] dp = new int[1001];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2; i < n; i++){
            dp[i] = (dp[i-1] + dp[i-2])%10007;
        }
        System.out.println(dp[n-1]);
    }
}

• 주의할 점 : 여기서 모듈러연산을 마지막 프린트 문에서 하면 오답이 나온다. 그 이유는 n이 특정 숫자를 넘어가면서부터 경우의 수가 int범위를 넘어가기 때문이다. 따라서 int배열에 저장하기 전에 모듈러연산을 처리하고 저장해야 한다.