[백준 10425] 피보나치 인버스

딱봤을 때,, 아무생각도 나지 않았고 일단 피보나치 수열부터 만들고 시작해야하나?라는 생각이 들었는데, 그렇게 푸는게 맞는 것 같다. 문제 분류가 이분탐색, 임의 정밀도/큰수 연산으로 되어 있었는데 이분탐색은 수열을 다 만들고 탐색할 때만 사용했다.

 

이 문제의 관건은 BigInteger를 쓸 수 있는가? 인것 같다.

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class 피보나치인버스 {
	static int T;
	static BigInteger Fn;
	static BigInteger[] fibo;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		fibo = new BigInteger[100001];
		fibo[0] = BigInteger.ZERO;
		fibo[1] = BigInteger.ONE;
		for(int i = 2; i <= 100000; i++) {
			fibo[i] = fibo[i-1].add(fibo[i-2]);
		}
		
		for(int t = 1; t <= T; t++) {
			Fn = new BigInteger(br.readLine());
			int result = find(Fn);
			System.out.println(result);
		}
	}

	private static int find(BigInteger num) {
		int left = 0;
		int right = fibo.length;
		
		while(true) {
			int mid = (left+right)/2;
//			System.out.println(mid);
			if(fibo[mid].compareTo(num)==1) {
				right = mid-1;
			}else if(fibo[mid].compareTo(num)==-1) {
				left = mid+1;
			}else {
				return mid;
			}
		}
		
	}

}