사용자 도구

사이트 도구


ps:problems:boj:2749

피보나치 수 3

ps
링크acmicpc.net/…
출처BOJ
문제 번호2749
문제명피보나치 수 3
레벨골드 2
분류

피보나치

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

풀이

  • 피보나치 수 (Fibonacci numbers)를 계산하는 문제. 피보나치 수 6와 n의 범위까지 동일하지만, 모듈러가 다르다.
  • 모듈러가 10^k 형태인데, 이 경우에는 피사노 주기가 15*10^(k-1)이 된다고 알려져 있다. 따라서 이 문제에서의 피사노 주기는 1,500,000이고, (n % 1,500,000)번째의 피보나치 수만 계산하는 것으로 문제를 바꿀 수 있다. 이렇게 범위를 줄여서 풀 경우에는 O(n) 알고리즘으로도 풀이가 가능하다
  • 하지만, 그냥 피보나치 수 6과 동일하게 O(logn) 알고리즘을 사용하면 피사노 주기를 활용하지 않고도 더 빠르게 풀수 있다.
    • 물론 피사노 주기를 활용해서 범위를 줄여놓고서 O(logn)알고리즘을 쓰면 좀더 빨라지지만, 이미 충분히 빨라서 큰 차이는 안난다. 시간이 100ms정도에서 70ms정도로 줄어드는 정도.

코드

"""Solution code for "BOJ 2749. 피보나치 수 3".

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

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 1_000_000
PISANO_PERIOD = 1_500_000


def main():
    n = int(input())
    print(combinatorics.fibonacci(n % PISANO_PERIOD, MOD))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M​ G S Q U
 
ps/problems/boj/2749.txt · 마지막으로 수정됨: 2024/03/28 14:35 저자 teferi