사용자 도구

사이트 도구


ps:problems:boj:11726

2×n 타일링

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

DP

시간복잡도O(logn)
인풋사이즈n<=1000
사용한 언어Python
제출기록29200KB / 80ms
최고기록52ms
해결날짜2021/07/30

풀이

  • 기초적인 DP문제. 그래서 변형 문제도 많다.
  • 2xn을 채우는 방법은 두가지로 나뉜다
    • 2x(n-1)을 채우고, 마지막에 2×1 타일을 붙이는 방법
    • 2x(n-2)을 채우고, 마지막에 1×2 타일 두개를 붙이는 방법
  • 따라서 점화식은 dp[n] = dp[n-2] + dp[n-1]처럼 되고, 이것은 피보나치 수 (Fibonacci numbers)의 점화식이므로, 답도 피보나치 수열이 된다.
  • n+1번째 피보나치 수 (Fibonacci numbers)를 구하면 되므로 시간복잡도는 O(logn).

코드

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

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

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 10007


def main():
    n = int(input())
    print(combinatorics.fibonacci(n + 1, MOD))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U J N F D
 
ps/problems/boj/11726.txt · 마지막으로 수정됨: 2021/07/31 16:30 저자 teferi