====== 타일 채우기 ======
  * 프로그래머스의 [[ps:problems:programmers:12902|3 x n 타일링]]과 동일한 문제이다.
  * BOJ의 [[ps:problems:boj:13976|타일 채우기 2]]도 동일한 문제이다
    * n의 범위만 다르다. 이 문제는 O(n)으로 풀어도 통과 가능하게 되어 있고, [[ps:problems:boj:13976|타일 채우기 2]]는 O(logn)으로 풀어야만 통과 가능하게 되어 있다.

===== 풀이 =====
  * N이 홀수이면, 3xN 을 채울 수 있는 방법은 없다
  * 중간에서 세로로 나누어지는 부분이 없는 3xN 타일링을 N-덩어리라고 부르자..
    * {{https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/upload/images/2663_1.jpg}} 
      * 이 예시는 2-덩어리, 4-덩어리, 2-덩어리, 4-덩어리로 이루어졌다
  * 2-덩어리를 만드는 방법은 3가지이다
  * 4-, 6-, 8-, ..., 덩어리를 만드는 방법은 2가지이다
  * 그러면 3xn 벽을 채우는 방법의 수, DP[n]은
    * 가장 마지막에 2-덩어리가 오는 방법의 수 => 3 * dp[n - 2]
    * 가장 마지막에 4-덩어리가 오는 방법의 수 => 2 * dp[n - 4]
    * 가장 마지막에 6-덩어리가 오는 방법의 수 => 2 * dp[n - 6]
    * ...
  * 이제 이것들을 다 더해서 dp[n]을 구할 수 있다.
    * <code>
dp[0] = 1
dp[n] = 3*dp[n-2] + 2*dp[n-4] + 2*dp[n-6] + ... + 2*dp[0] = 3*dp[n-2] + 2*sum(dp[0:n-3:2])
</code>
      * 이렇게 하면 테이블 한칸을 채우는데에 O(n)이니까, 테이블을 전부 채우는데에는 O(n^2)
    * 하지만, sum부분을 다시 정리하면
      * <code>
2*sum(dp[0:n-3:2]) = 2*dp[n-4] + 2*dp[n-6] + 2*dp[n-8] + ... + 2*dp[0]
                   = (3*dp[n-4] + 2*dp[n-6] + 2*dp[n-8] + ... + 2*dp[0]) - dp[n-4]
                   = dp[n-2] - dp[n-4]
</code>
  * 대입하면 ''%%dp[n] = 3*dp[n-2] + (dp[n-2] - dp[n-4]) = 4*dp[n-2] - dp[n-4]%%'' 가 된다
    * [[ps:선형_점화식#상수계수의 선형 점화식]]이므로, 단순히 풀면 O(n) 시간에, 행렬곱을 이용하면 O(logn) 시간에 풀이가 가능해진다
  * 사실 이 문제에서는 n이 워낙 작아서, O(n^2)으로 풀든 O(n)으로 풀든, O(logn)에 풀든 시간 차이가 거의 안난다. 
    * 미리 30까지 테이블을 계산해서 코드에 넣어놓고 O(1)에 출력할 수도 있다.

===== 코드 =====

==== 코드 1 ====
<dkpr py>
"""Solution code for "BOJ 2133. 타일 채우기".

- Problem link: https://www.acmicpc.net/problem/2133
- Solution link: http://www.teferi.net/ps/problems/boj/2133
"""

from teflib import combinatorics


def main():
    n = int(input())
    print(0 if n % 2
          else combinatorics.linear_homogeneous_recurrence([4, -1], [1, 3],
                                                           n // 2))


if __name__ == '__main__':
    main()
</dkpr>

  * Dependency: [[:ps:teflib:combinatorics#linear_homogeneous_recurrence|teflib.combinatorics.linear_homogeneous_recurrence]]

==== 코드 2 - 행렬곱 기법을 쓰지 않고 O(n)으로 푸는 방식 ====
<dkpr py>
def main():
    n = int(input())
    if n % 2:
        print(0)
    else:
        cur, prev = 3, 1
        for i in range(2, n, 2):
            cur, prev = cur * 4 - prev, cur
        print(cur)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:BOJ:실버_2}}