사용자 도구

사이트 도구


ps:problems:boj:13976

타일 채우기 2

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

동적계획법

시간복잡도O(logn)
인풋사이즈n<=10^18
사용한 언어Python
제출기록33944KB / 148ms
최고기록56ms
해결날짜2021/01/11
  • 타일 채우기 문제에서 n의 범위만 증가시킨 문제.
    • 타일 채우기는 O(n)으로 풀어도 통과 가능하게 되어 있고, 이 문제는 O(logn)으로 풀어야만 통과 가능하게 되어 있다.

풀이

코드

"""Solution code for "BOJ 13976. 타일 채우기 2".

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

from teflib import combinatorics

MOD = 1_000_000_007


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


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L Z X H C
 
ps/problems/boj/13976.txt · 마지막으로 수정됨: 2021/01/12 04:10 저자 teferi