문제링크

풀이

dp 배열에 가로 n번째까지 타일을 채울 수 있는 최대 방법의 수를 저장한다.
세가지 종류의 타일을 각각 가로(1x2), 세로(2x1), 정사각형(2x2)라고 칭하겠다.
n = 1 일 때, 직사각형의 크기가 2x1 이므로 세로 타일 하나만 채울 수 있다.
n = 2 일 때, 직사각형의 크기는 2x2가 되고 세로*2, 가로*2, 정사각형 세가지로 채울 수 있다.

n = 3 부터 n까지는 두 가지 상황으로 나누어 계산을 해주면 된다.
1. n-1까지 채워진 상태에서 n번째에 세로 타일을 채우는 상황
2. n-2까지 채워진 상태에서 남은 2*2에 타일을 채우는 상황

1번 상황의 경우 이전에 n-1 번째까지 채울 수 있는 최대 방법이 dp[n-1]에 저장되어있기 때문에 그냥 더해주면된다.
2번 상황의 경우에는 한가지 주의할 점이 있다. 2x2를 채우는 경우의 수는세로*2, 가로*2, 정사각형 로 세가지이지만, 세로*2로 채우는 경우는 제외시켜야한다. 그 이유는 이미 1번 상황에서 그 경우를 포함하기 때문이다.

위 풀이를 토대로 점화식을 작성하면 다음과 같다.

dp[i] = dp[i - 1] + dp[i - 2] * 2;

코드

package BOJ;

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

public class sol11727 {
    static int n;
    static int[] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        if (n == 1) {
            System.out.println(1);
            return;
        }
        dp = new int[n + 1];

        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;	// 수가 커져 int 범위를 넘어설 수 있기 때문에 나머지 연산을 미리 해준다. 
        }

        System.out.println(dp[n]);
    }
}

주의할 점

n==1인 경우를 예외적으로 처리해주지 않으면 ArrayIndexOutOfBounds 에러가 발생한다.
dp배열의 사이즈를 n+1로 초기화하기 때문에 n==1일 경우 이후 코드에서 dp[2]에 접근하며 오류가 발생.

풀 수 있는 문제더라도 저런 값을 처리하지 않아 틀리는 일이 없도록, 위와 같은 경계값 처리를 주의해야겠다.