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

2025. 2. 24. 11:00·Algorithm/백준 (BOJ)
반응형

💻 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

반응형

'Algorithm > 백준 (BOJ)' 카테고리의 다른 글

[Python] 백준/BOJ 9019번: DSLR (Gold 4)  (0) 2025.02.26
[Python] 백준/BOJ 30804번: 과일 탕후루 (Silver 2)  (0) 2025.02.25
[Python] 백준/BOJ 15810번: 풍선 공장 (Silver 2)  (0) 2025.02.23
[Python] 백준/BOJ 7662번: 이중 우선순위 큐 (Gold 4)  (0) 2025.02.22
'Algorithm/백준 (BOJ)' 카테고리의 다른 글
  • [Python] 백준/BOJ 9019번: DSLR (Gold 4)
  • [Python] 백준/BOJ 30804번: 과일 탕후루 (Silver 2)
  • [Python] 백준/BOJ 15810번: 풍선 공장 (Silver 2)
  • [Python] 백준/BOJ 7662번: 이중 우선순위 큐 (Gold 4)
올콩
올콩
콩 심은 데 콩 난다
  • 올콩
    콩스토리
    올콩
  • 전체
    오늘
    어제
    • 분류 전체보기 (196) N
      • SSAFY (10)
      • Algorithm (114) N
        • 이론 (6)
        • 백준 (BOJ) (107) N
        • 프로그래머스 (1)
      • Trouble Shooting (9)
      • Frontend (6)
      • React (17)
      • Next.js (4)
      • Vue (4)
      • Node.js (2)
      • HTML (9)
      • DevOps (4)
        • Git (4)
      • Language (9)
        • JavaScript (0)
        • Java (9)
      • Embedded (1)
      • CS (5)
        • Network (1)
        • Blockchain (4)
      • 자격증 (2)
  • 블로그 메뉴

    • GitHub
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    SSAFY
    Algorithm
    알고리즘
    Java
    SSAFYcial
    브루트포스
    Heap
    강의
    파이썬
    힙
    중복순열
    중복조합
    구현
    우선순위큐
    티스토리챌린지
    오블완
    순열
    백트래킹
    DP
    bfs
    재귀
    싸피
    React
    html5
    수학
    블록체인
    dfs
    Error
    백준
    Next.js
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
올콩
[Python] 백준/BOJ 10425번: 피보나치 인버스 (Silver 2)
상단으로

티스토리툴바