대칭을 신경쓰지 않는 경우를 먼저 살펴봅니다.

2×N 크기 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우는 경우의 수를 $F(N)$이라고 하겠습니다.

왼쪽부터 $N$번째 위치에 타일을 오른쪽 정렬하여 놓는다고 생각하면 경우의 수가 좁혀집니다.

  • 1×2 타일을 하나 두는 경우

    • 왼쪽 $N - 1$개의 타일은 자유롭게 놓을 수 있으므로 $F(N - 1)$가지입니다.

  • 2×1 타일을 두 개 두는 경우

    • 왼쪽 $N - 2$개의 타일은 자유롭게 놓을 수 있으므로 $F(N - 2)$가지입니다.

  • 2×2 타일을 하나 두는 경우

    • 왼쪽 $N - 2$개의 타일은 자유롭게 놓을 수 있으므로 $F(N - 2)$가지입니다.

이에 따라 $F(N)$을 다음과 같이 놓을 수 있습니다.

$$ F(N) = \begin{cases} 1 & \left(N = 1\right) \\ 3 & \left(N = 2\right) \\ F(N - 1) + 2F(N - 2) & \text{otherwise.} \end{cases} $$

$N$을 1부터 목푯값까지 늘려가며 계산하면 $O\left(N\right)$ 시간에 답을 구할 수 있습니다.

다음으로 대칭인 경우를 따지기 위해서 다시 경우를 나누어 봅니다.

특정 배열이 그 자체로 대칭인 경우를 제외하면, 그 배열을 가로로 뒤집은 배열도 전체 경우의 수 안에 반드시 존재합니다.

즉 대칭을 제외한 경우의 수 = 자신이 대칭인 경우의 수 + (나머지 경우의 수) / 2

변형하면 (자신이 대칭인 경우의 수 + 전체 경우의 수) / 2로도 쓸 수 있습니다.

전체 경우의 수는 계산할 수 있으므로 대칭인 경우의 수를 세어야 합니다. 이때 중간에 가로가 2인 타일이 포함될 수 있으므로 홀짝을 나누어 세어야 한다는 것을 알 수 있습니다.

  • $N$이 짝수인 경우

    • $N/2$ 크기의 배열을 하나 정하고, 이를 뒤집어 붙인 경우
    • $\left(N/2\right) - 1$ 크기의 배열을 하나 정하고, 이를 뒤집어 붙이되 둘 사이에 2×1 크기 타일을 두 개 붙인 경우
    • $\left(N/2\right) - 1$ 크기의 배열을 하나 정하고, 이를 뒤집어 붙이되 둘 사이에 2×2 크기 타일을 하나 붙인 경우

  • $N$이 홀수인 경우

    • $\left(N - 1\right)/2$ 크기의 배열을 하나 정하고, 이를 뒤집어 붙이되 둘 사이에 1×2 크기 타일을 하나 붙인 경우

전체 경우의 수를 계산할 때 입력값보다 작은 $N$에 대해서 구한 값을 저장해 뒀다면, 대칭인 경우의 수를 구하는 것은 재계산이 필요 없이 $O(1)$로 해결이 가능합니다.

코드 
fn solve(size: usize) -> usize {
    let mut count = vec![0; size + 1];
    count[0] = 1;
    count[1] = 1;
    for i in 2..=size {
        count[i] = count[i - 2] * 2 + count[i - 1];
    }
    let mut result = count[size];
    result += count[size / 2];
    if size % 2 == 0 {
        result += count[size / 2 - 1] * 2;
    }
    result / 2
}