<java> 백준 11834 - 이진탐색

 

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

 

이 문제는 이진 탐색을 가장한 수학 문제이다.

 

 

일단 배열을 나열해 보면

마지막 숫자들이 속한 그룹(n)의 제곱임을 알 수있다.

 

또한 그룹 내부에서도

자신 그룹의 첫번째 숫자를 1 이라고 할때 2씩 커지기 때문에

이전그룹의 마지막 숫자에서 현재 그룹에서의 index를 구해서

2*index -1을 해주면 문제를 풀 수 있다.

 

해당 풀이를 식으로 구현해 보면 (I는 입력받은 숫자이다.)

답이 2*I -n으로 간단하게 나온다

 

단 I가 10의 100승으로 아주 크기 때문에

모든 숫자는 BigInteger로 처리해 주어야 하고

n을 구할때도 이진 탐색으로 구현하여 시간을 최대한 줄여주어야 한다.

정답

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

public class Q11834 {

    static BigInteger N, n, answer;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        N = new BigInteger(reader.readLine());
        n = findSmallN(N); // n(n+1)/2 = N 만족하는 n

        answer = N.multiply(BigInteger.TWO).subtract(n);

        writer.write(answer.toString());
        writer.flush();
        writer.close();
    }

    static BigInteger findSmallN(BigInteger target){
        BigInteger start = new BigInteger(String.valueOf(1));
        BigInteger end = new BigInteger("1" + "0".repeat(100));
        while(start.compareTo(end) == -1){
            BigInteger mid = start.add(end.subtract(start).divide(BigInteger.TWO));
            if(calcSum(mid).compareTo(target) == -1){
                start = mid.add(BigInteger.ONE);
            }else{
                end = mid;
            }
        }
        return start;
    }

    static BigInteger calcSum(BigInteger mid){
        return (mid.multiply (mid.add(BigInteger.ONE))).divide(BigInteger.TWO);
    }



}