[BOJ, 백준] 10425 - 피보나치 인버스 (Python)

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

문제

Fn={0if n = 0;1if n = 1;Fn−1+Fn−2if n > 1.

 

피보나치 수는 수학에서 위의 점화식으로 정의되는 수열이다. 피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다. n = 0, 1,...에 해당하는 피보나치 수는 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946… 이다.

프로그래밍 실습에서 문제 중 n을 입력 받았을 때 Fn의 값을 출력하는 문제가 자주 등장한다. 실습을 하고 있던 희원이는 문득 이 문제가 너무 쉽다고 생각했다. 희원이는 실습 도중 반대로 Fn이 주어졌을 때 n을 출력하는 문제는 어떨지 궁금했다. 피보나치 수 Fn이 주어졌을 때 n을 출력하는 프로그램을 만들어 보자.

 

입력

첫 번째 줄에 테스트케이스를 나타내는 T(1 ≤ T ≤ 100)가 입력으로 주어진다. 두 번째 줄부터 각 테스트케이스마다 양의 정수 Fn이 입력으로 주어진다. (1 ≤ Fn ≤ 1021000, 1 ≤ N ≤ 100,000)

출력

피보나치 수 Fn이 주어졌을 때 n을 출력한다. 만약 가능한 경우가 여러 개 있는 경우에는 가장 큰 인덱스를 출력하라. 피보나치 수가 아닌 수가 들어오는 경우는 없다.

예제 입출력

풀이

# 피보나치 인버스, 10425.py
# 출처: University > 서강대학교 > 2014 Sogang Programming Contest - Master G번, University > 서강대학교 > 2014 Sogang Programming Contest - Champion G번
# 알고리즘 분류: 수학, 이분 탐색, 임의 정밀도 / 큰 수 연산
import sys
input = sys.stdin.readline
fibo = [0,1]
dict = {}
for i in range(0,100000):
    fibo.append(fibo[i+1]+fibo[i])
    dict[fibo[i+2]]=i+2
t=int(input())
for i in range(t):
    fn = int(input())
    if fn == 1:
        print(2)
    else:
        print(dict[fn])

 

빠른 검색을 위하여 dictionary를 이용했다.

숫자가 커서 시간초과가 나지 않을까 걱정했는데 잘 통과했다.

파이썬의 좋은점이 잘 나타나는 문제인것 같다.

다른 언어라면 biginteger를 구현했어야됬을 것 같은데 파이썬은 그럴 필요없으니까 쉽게 풀 수 있었다.