사용자 도구

사이트 도구


ps:problems:boj:2133

타일 채우기

ps
링크https://www.acmicpc.net/problem/2133
출처BOJ
문제 번호2133
문제명타일 채우기
레벨실버 2
분류

동적계획법

시간복잡도O(logn)
인풋사이즈n<=30
사용한 언어Python
제출기록33952KB / 140ms
최고기록64ms
해결날짜2020/11/12
  • 프로그래머스의 3 x n 타일링과 동일한 문제이다.
  • BOJ의 타일 채우기 2도 동일한 문제이다
    • n의 범위만 다르다. 이 문제는 O(n)으로 풀어도 통과 가능하게 되어 있고, 타일 채우기 2는 O(logn)으로 풀어야만 통과 가능하게 되어 있다.

풀이

  • N이 홀수이면, 3xN 을 채울 수 있는 방법은 없다
  • 중간에서 세로로 나누어지는 부분이 없는 3xN 타일링을 N-덩어리라고 부르자..
    • 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]을 구할 수 있다.
    • 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] 가 된다
  • 사실 이 문제에서는 n이 워낙 작아서, O(n^2)으로 풀든 O(n)으로 풀든, O(logn)에 풀든 시간 차이가 거의 안난다.
    • 미리 30까지 테이블을 계산해서 코드에 넣어놓고 O(1)에 출력할 수도 있다.

코드

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

코드 2 - 행렬곱 기법을 쓰지 않고 O(n)으로 푸는 방식

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

토론

댓글을 입력하세요:
F K W Q O
 
ps/problems/boj/2133.txt · 마지막으로 수정됨: 2021/01/12 04:25 저자 teferi