백준 10425 - 피보나치 인버스 (자바 - 이분탐색)

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

10425번: 피보나치 인버스

 

* 문제 요약

피보나치 수는 수학에서 위의 점화식으로 정의되는 수열이다. 피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다.

n = 0, 1, ... 에 해당하는 피보나치 수는 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... 이다.

프로그래밍 실습에서 문제 중 n을 입력받았을 때 Fn 의 값을 출력하는 문제가 자주 등장한다. 실습을 하고 있던 희원이는 문득 이 문제가 너무 쉽다고 생각했다.

희원이는 실습 도중 반대로 Fn 이 주어졌을 때 n을 출력하는 문제는 어떨지 궁금했다. 피보나치 수 Fn 이 주어졌을 때 출력하는 프로그램을 만들어보자.

 

 * 입력

첫 번째 줄에 테스트케이스를 나타내는 T (1 <= T <= 100) 가 입력으로 주어진다.

두 번째 줄부터 각 테스트케이스마다 양의 정수 Fn 이 입력으로 주어진다. (1 <= Fn <= 10^21000, 1 <= N <= 100,000)

 

* 출력

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

 

* 예시

 

* 해결 과정

인덱스 0 ~ 100,000 까지의 BigInteger 타입의 배열을 만들고, 해당 배열의 각 인덱스 값들을 DP 알고리즘을 이용해 만들어진 피보나치 수열 값으로 저장한다.

이후 각 테스트 케이스마다 입력된 값을 UpperBound(중복이 존재하는 배열에서 특정값이 존재하는 마지막 인덱스 찾기) 방식의 이분탐색을 활용하여 해당 값이 저장된 인덱스를 찾아주었다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    static BigInteger[] fibonacci = new BigInteger[100001];

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());

        fibonacci[0] = new BigInteger("0");
        fibonacci[1] = new BigInteger("1");

        for (int i = 2; i < fibonacci.length; i++) {
            fibonacci[i] = fibonacci[i - 1].add(fibonacci[i - 2]);
        }

        for (int i = 0; i < tc; i++) {
            BigInteger fn = new BigInteger(br.readLine());

            int index = upperBound(fn);
            bw.write(index + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private int upperBound(BigInteger fn) {

        int start = 0;
        int end = fibonacci.length;
        while (start < end) {
            int mid = (start + end) / 2;

            if (fn.compareTo(fibonacci[mid]) == 0 || fn.compareTo(fibonacci[mid]) == 1) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start - 1;
    }
}

 

조금 무식하지만 문제에서 조건으로 제시된 100,000 크기만큼의 피보나치 수열을 만들어서 배열에 저장한 다음, 해당 배열을 대상으로 mid 인덱스에 해당하는 값이 찾고자 하는 값 보다 작은지, 또는 크거나 같은지에 따라 범위를 줄여가며 답을 찾았으므로 이분탐색 문제에 해당된다.