[백준] 10452 : 피보나치 인버스

www.acmicpc.net/problem/10425

10425번: 피보나치 인버스

---

• 피보나치값의 범위가 10의 21000 승이므로 단순한 자료형으로는 절대 풀 수 없다.
• 원래는 자릿수와 가장 큰 자리의 값을 키로 하려고 했지만, 뒤의 x 자리를 키로 하는게 더 계산하기가 편했다.
• 딕셔너리와 문자열 슬라이싱 등을 사용하는데 파이썬이 너무 좋은 것 같다.
• 다른 사람들 풀이를 보니 파이썬의 경우 굳이 20자리만 볼 것이 아니라 전체 값을 해도 되는 듯 하다.
• 물론 정수 자료형의 범위가 무한대이긴 해도 진짜 가능할 줄은 몰랐는데...

---

import sys

T = input()

fib = {}
fib[0] = bef2 = 0
fib[1] = bef1 = 1

for i in range(2, 100001):
    val = str(bef2 + bef1)[-21:]    # n 번째 피보나치의 마지막 20자리를 키로 해서
    fib[val] = i                    # n 을 값으로 넣음
    bef2 = bef1                     # 다음 피보나치 업데이트
    bef1 = int(val)

for line in sys.stdin:
    print(fib[line.strip()[-21:]])  # 입력받은 피보나치값의 마지막 20자리로 n 을 구함