사용자 도구

사이트 도구


ps:problems:boj:11727

2×n 타일링 2

ps
링크acmicpc.net/…
출처BOJ
문제 번호11727
문제명2×n 타일링 2
레벨실버 3
분류

DP

시간복잡도O(logn)
인풋사이즈n<=1,000
사용한 언어Python
제출기록33988KB / 184ms
최고기록52ms
해결날짜2021/07/31

풀이

  • 2×n 타일링의 변형. 2×2 블럭이 추가되었다.
  • 이제 2xn크기를 채우는 방법은 아래의 세가지 경우로 나뉜다
    • 2x(n-1) 을 채우고 2×1 블럭을 마지막에 붙이는 방법
    • 2x(n-2) 을 채우고 1×2 블럭 두개를 마지막에 붙이는 방법
    • 2x(n-2) 을 채우고 2×2 블럭을 마지막에 붙이는 방법
  • 점화식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-2] = 1*DP[n-1] + 2*DP[n-2]
  • 그냥 O(n)에 계산해도 되고, 상수계수의 선형 점화식을 행렬곱으로 푸는 방법을 이용해서 O(logn)에 계산할수도 있다. n이 크지 않아서 실제 시간은 O(n)방법이 더 빨리 돌아가는것 같다

코드

"""Solution code for "BOJ 11727. 2×n 타일링 2".

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

Tags: [DP] [LinearHomogeneousRecurrence]
"""

from teflib import combinatorics

MOD = 10007


def main():
    n = int(input())
    print(combinatorics.linear_homogeneous_recurrence([1, 2], [1, 1], n, MOD))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
T E L X L
 
ps/problems/boj/11727.txt · 마지막으로 수정됨: 2021/07/31 16:32 저자 teferi