[Python] 백준/BOJ 10425번: 피보나치 인버스 (Silver 2)

💻 Problem

문제 보러 가기

 

피보나치 수는 수학에서 위의 점화식으로 정의되는 수열이다. 피보나치 수는 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을 출력하는 프로그램을 만들어 보자.

 

💡 Approach

n번째 피보나치 수 Fn이 주어지면, Fn이 몇 번째 피보나치 수인지 구하는 문제이다.

 

먼저 피보나치 수 배열을 만든다.

피보나치 수 배열에서 인덱스를 가지고 이분탐색을 진행한다.

해당 인덱스의 피보나치 수가 입력받은 Fn이 될 때까지 찾는다.

 

만약 가능한 경우가 여러 개면 가장 큰 인덱스를 출력하라고 나와있다.

피보나치 수는 Fn-1과 Fn-2를 더하므로 Fn 값이 같은 경우는 n이 1이나 2일 경우밖에 없다.

F1은 1이고 F2는 1 + 0 = 1이므로..

그래서 답이 1인 경우에만 예외적으로 2를 출력하도록 했다.

 

✏️ Solution

• 반열린구간 이분탐색 (start, end]

import sys
input = sys.stdin.readline

MAX = 10 ** 21000
fibo = [0, 1]
num = 0
# 피보나치 수 배열 만들기
while num <= MAX:
    num = fibo[-1] + fibo[-2]
    fibo.append(num)

t = int(input())
for _ in range(t):
    f = int(input()) # 피보나치 수 Fn
    start, end = -1, len(fibo) - 1 # (s, e]

    while start + 1 < end:
        mid = (start + end) // 2

        # 현재 mid의 피보나치 수가 Fn보다 작으면 오른쪽 탐색
        if fibo[mid] < f:
            start = mid
        # 현재 mid의 피보나치 수가 Fn보다 크면 왼쪽 탐색
        else:
            end = mid
    
    # end가 1일 때는 인덱스가 가장 큰 2를 출력
    print(end if end != 1 else 2)

• 반열린구간 이분탐색 [start, end)

import sys
input = sys.stdin.readline

MAX = 10 ** 21000
fibo = [0, 1]
num = 0
# 피보나치 수 배열 만들기
while num <= MAX:
    num = fibo[-1] + fibo[-2]
    fibo.append(num)

t = int(input())
for _ in range(t):
    f = int(input()) # 피보나치 수 Fn
    start, end = 0, len(fibo) # [s, e)

    while start + 1 < end:
        mid = (start + end) // 2

        # 현재 mid의 피보나치 수가 Fn보다 작으면 오른쪽 탐색
        if fibo[mid] <= f:
            start = mid
        # 현재 mid의 피보나치 수가 Fn보다 크면 왼쪽 탐색
        else:
            end = mid
    
    # end가 1일 때는 인덱스가 가장 큰 2를 출력
    print(start if end != 1 else 2)

이 문제는 최솟값이나 최댓값을 찾는 문제가 아니라 특정 위치를 찾는 문제이기 때문에 앞에서 열든 뒤에서 열든 상관없다.

start를 열었을 때의 코드와 end를 열었을 때의 코드를 각각 작성해 보았다.

 

이분탐색의 시간복잡도는 O(log n)이다.

테스트케이스의 최댓값은 10^2, n의 최댓값은 10^5이므로 전체 시간복잡도는 10^2 * log 10^5이다.

10^2 * log 10^5 = 10^2 * log 2^16 = 100 * 16 = 1600