[백준 3020] 개똥벌레(Java)

문제 링크 : https://www.acmicpc.net/problem/3020

이 문제는 이진 탐색 또는 누적합을 이용하여 풀 수 있습니다.

먼저 이진 탐색을 이용하여 푸는 방법을 알아보겠습니다. 만약 완전 탐색으로 진행한다면 다음의 과정을 진행합니다.

1. 위와 아래의 장애물 위치별 길이를 저장
2. 1부터 H까지 포인터를 이동하면서 N개를 탐색하면서 해당 높이보다 큰 값을 갖는 항목을 ++
3. 위 아래를 각각 진행하여 최솟값 구하기

이 때 2번 과정의 경우 HxN 의 시간 복잡도를 가져 시간초과가 발생합니다. 따라서 이 부분을 줄이기 위해 이진 탐색을 진행합니다. 장애물 위치가 중요하지 않기 때문에 오름차순 정렬한 후 양 끝을 포인터로 하여 중간값이 현재 높이값과 일치했을 때의 장애물의 개수를 구하면 시간 복잡도를 단축할 수 있습니다.

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

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

        int N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        int[] up = new int[N/2];
        int[] down = new int[N/2];
        for(int i=0;i<N;i++){
            if(i%2==0) down[i/2] = Integer.parseInt(br.readLine());
            else up[i/2] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(up);
        Arrays.sort(down);

        int min = Integer.MAX_VALUE;
        int num = 0;
        for(int i=1;i<=H;i++){
            int d = calc(0,N/2,down,i);
            int u = calc(0,N/2,up,H-i+1);

            if(min > d+u){
                min = d+u;
                num = 1;
            }
            else if(min == d+u) num++;
        }

        System.out.println(min+" "+num);
    }

    static int calc(int left, int right, int[] arr, int h){
        while(left<right){
            int mid = (left+right)/2;

            if(arr[mid] >= h) right = mid;
            else left = mid+1;
        }
        return arr.length-right;
    }
}

누적합 풀이의 경우 위와 아래의 장애물 위치별 길이를 저장하는 대신 장애물 높이별 카운트를 진행합니다. 이 후 각 높이의 누적합을 구한다면 특정 높이 사이의 장애물의 개수는 누적합의 차로 구할 수 있습니다. 이를 이용하여 장애물의 개수가 최소가 되는 조건을 만족하는 값을 구합니다.

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

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

        int N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        int[] down = new int[H+2];
        int[] up = new int[H+2];

        for(int i=0;i<N/2;i++){
            int d = Integer.parseInt(br.readLine());
            int u = H-Integer.parseInt(br.readLine())+1;
            down[d]++;
            up[u]++;
        }

        for(int i=1;i<=H;i++) down[i] += down[i-1];
        for(int i=H;i>=1;i--) up[i] += up[i+1];

        int min = Integer.MAX_VALUE;
        int num = 0;
        for(int i=1;i<=H;i++){
            int d = down[H]-down[i-1];
            int u = up[1]-up[i+1];

            if(min > d+u){
                min = d+u;
                num = 1;
            }
            else if(min == d+u) num++;
        }

        System.out.println(min+" "+num);
    }
}