99클럽 코테 스터디 2일차 TIL 이분탐색(징검다리)

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

 

 

 

처음에 이분탐색이라는 아이디어를 떠올리는 게 어려운 문제였다,,

근데 자세히 보면 N의 범위로 보아 선형탐색은 절대 아니고, 두 번째 점프부터 이전 점프 + 1 긴 거리를 점프한다는 점에서 등차수열을 떠올릴 수 있다.

그리고 최대 수이니 결국은 무조건 다음 식을 만족한다. => 다음 점프 = (이전 점프 + 1)

그렇다면, 몇 개의 징검다리를 건넜을 때가 최대 징검다리가 될 까? 이 징검다리 수를 m으로 두고 이분탐색을 통해 조건을 만족하는 최대 m 값을 구하면 된다.

그리고 조건은, m * (m + 1) / 2기 N의 값에 가장 가까우면 된다. (등차수열의 합 공식 사용)

주의점은 N의 최대 범위를 고려하여 자료형을 long으로 사용해야 한다.

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_11561 {

    static int T;
    static long N;
    static long ans;

    public static void binarySearch(long s, long e, long target){
        if(s > e) return;
        long m = (s + e) / 2;
        long sum = m * (m + 1) / 2;
        if(sum <= target) {
            ans = m;
            binarySearch(m+1, e, target);
        }else{
            binarySearch(s, m-1, target);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        T = Integer.parseInt(st.nextToken());
        while(T --> 0){
            st = new StringTokenizer(br.readLine());
            N = Long.parseLong(st.nextToken());
            binarySearch(0, (long)Math.sqrt(2*N-1), N);
            System.out.println(ans);
        }
    }
}