[파이썬/python] 백준 - 10425 피보나치 인버스

문제

https://www.acmicpc.net/problem/10425

---

문제 설명

1. n번째 피보나치 수 $F_n$이 주어진다.
2. $F_n$이 몇 번째 피보나치 수인지 구한다.
   1. 이 때 가능한 경우가 여러 개라면 가장 큰 인덱스를 출력한다.

 

---

풀이

1. $F_n$의 최댓값이 $10^{21000}$ 이므로 10**21000까지의 피보나치 수를 구한다.
2. 이분탐색을 통해 mid 인덱스의 피보나치 수와 $F_n$을 비교한다.
   1. fibo[mid]가 $F_n$보다 작다면 s = mid 크거나 같다면 e = mid로 바꾸어 범위를 줄인다.
3. 마지막으로 나온 값(인덱스)을 출력한다.

---

코드

import sys
input = sys.stdin.readline

fibo = [0,1,1,2,3]
MAX = (10**21000)
num = 0
while num <= MAX:
    num = fibo[-1] + fibo[-2]
    fibo.append(num)



for tc in range(int(input())):
    n = int(input())
    s = 0
    e = len(fibo) + 1
    while s+1 < e:
        mid = (s + e) //2
        if fibo[mid] < n:
            s = mid
        else:
            e = mid
    if e == 1:
        e = 2
    print(e)

---

시간복잡도

• $10^{21000}$까지의 피보나치수를 구하는데 시간복잡도는 약 $O(10^5)$
• 이분탐색의 시간복잡도는 $O(log_N)$
• 최악의 경우 $N = 10^{12}$이므로 약 $O(10^5 + 40)$의 시간복잡도를 가진다.