(Java) 백준 11727번 - 2xn 타일링 2

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

문제

> 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
> 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

접근

2x1을 만드는 경우는 2x1짜리로 만드는 1가지,
2x2는 2x1짜리 2개로 1가지 + 1x2짜리 2개로 1가지 + 2x2짜리 1개로 1가지 해서 총 3가지이다.
2x3은 2x1 3개로 1가지 + 2x1 1개와 1x2 2개로 만드는 2가지 + 2x1 1개와 2x2 1개로 만드는 2가지 해서 총 5가지 이다.
이 같은 방식으로 하니씩 그려보며 2x5까지 구해보면 경우의 수가 수열로
1, 3, 5, 11, 21이 된다. 이를 통해 규칙을 찾아보면
i번째는 i-1번째의 경우의 수 + i-2번쨰 경우의 수의 2배가 된다.
ex 11 = 5 + 3x2, 21 = 11 + 5x2

문제해결

> DP를 사용하여 경우의 수를 따져 각 N에 대한 경우의 수를 dp(N)에 저장하기 위한 배열을 선언한다.
> 2x1과 2x2를 만드는 경우의 초기값을 먼저 넣어준다.
> 2x3부터는 앞서 유도한 점화식으로 입력받은 N까지 구한다.
> dp(i)에 대해 dp(i-1) + dp(i-2) x 2로 구한 뒤 문제의 조건인 10007로 나머지 연산 해준다.

코드

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main
{
    //11727번 2xn 타일링 2
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 3;
        for(int i = 3; i <= N; i++) dp[i] = (dp[i-1] + dp[i-2] * 2) % 10007;

        System.out.print(dp[N]);
    }
}

후기

아무리 해도 규칙을 찾을 수 없어 고민하다가 다시 그려봤는데 처음에 경우의 수를 잘못 구했었다. 처음엔 무슨 이유로 잘못 구했는지..
잘 구했는데 틀려서 또 뭐가 문제인가 봤더니 10007로 나머지연산을 하지 않았다. 잊지말고 잘 읽자