타일 채우기

• 프로그래머스의 3 x n 타일링과 동일한 문제이다.
• BOJ의 타일 채우기 2도 동일한 문제이다
  • n의 범위만 다르다. 이 문제는 O(n)으로 풀어도 통과 가능하게 되어 있고, 타일 채우기 2는 O(logn)으로 풀어야만 통과 가능하게 되어 있다.

• N이 홀수이면, 3xN 을 채울 수 있는 방법은 없다
• 중간에서 세로로 나누어지는 부분이 없는 3xN 타일링을 N-덩어리라고 부르자..
  • 
    • 이 예시는 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]을 구할 수 있다.

  • 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])

    • 이렇게 하면 테이블 한칸을 채우는데에 O(n)이니까, 테이블을 전부 채우는데에는 O(n^2)
  • 하지만, sum부분을 다시 정리하면

    • 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]

• 대입하면 dp[n] = 3*dp[n-2] + (dp[n-2] - dp[n-4]) = 4*dp[n-2] - dp[n-4] 가 된다
  • 상수계수의 선형 점화식이므로, 단순히 풀면 O(n) 시간에, 행렬곱을 이용하면 O(logn) 시간에 풀이가 가능해진다
• 사실 이 문제에서는 n이 워낙 작아서, O(n^2)으로 풀든 O(n)으로 풀든, O(logn)에 풀든 시간 차이가 거의 안난다.
  • 미리 30까지 테이블을 계산해서 코드에 넣어놓고 O(1)에 출력할 수도 있다.

"""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()

• Dependency: teflib.combinatorics.linear_homogeneous_recurrence

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()