[JAVA] [이진탐색] 백준 3020 개똥벌레

문제

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

3020번: 개똥벌레

코드

import java.io.*;
import java.util.*;

public class b3020 {
    static int[] seog; // 석순
    static int[] jong; // 종유석
    static int h;

    private static int upper(int target){
        int start=0;
        int end=jong.length;
        while(start<end){
            int mid=(start+end)/2;
            if(jong[mid]>target){
                end=mid;
            }
            else{
                start=mid+1;
            }
        }
        return start;
    }

    private static int lower(int target){
        int start=0;
        int end=seog.length;

        while(start<end){
            int mid=(start+end)/2;
            if(seog[mid]>=target){
                end=mid;
            }
            else{
                start=mid+1;
            }
        }
        return start;
        
    }

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

        st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        h=Integer.parseInt(st.nextToken());

        seog=new int[n/2];
        jong=new int[n/2];
        for(int i=0; i<n; i++){
            if(i%2==0) seog[i/2]=Integer.parseInt(br.readLine());
            else jong[i/2]=Integer.parseInt(br.readLine());
        }

        Arrays.sort(seog);
        Arrays.sort(jong);

        int destroy=99999999;
        int count=99999999;
        for(int i=1; i<=h; i++){
            // 현재가 i 구간일 때
            // 석순은 (n/2)-i의 lowerBound 만큼 파괴
            int tempA=(n/2)-lower(i);
            // 종유석은 (n/2) - (h-i)의 upperBound 만큼 파괴
            int tempB=(n/2)-upper(h-i);
            if(destroy>(tempA+tempB)){
                destroy=tempA+tempB;
                count=1;
            }
            else if(destroy==(tempA+tempB)){
                count++;
            }
        }
        System.out.println(destroy+" "+count);
    }
}

소요시간

2시간

 

어려웠던 부분

석순이랑 종유석을 따로 계산하는거랑 어떤걸 기준으로 이진 탐색할지 찾는데 시간이 오래 걸렸다.