백준 3020[자바] jav 개똥벌레

 

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

3020번: 개똥벌레

 

▶문제

 

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득 찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟 개다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

 

▶입력

 

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

 

▶출력

 

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

 

▶해설

 

이분탐색, 누적합으로 풀 수 있습니다. 이분 탐색을 활용해서 풀어보겠습니다. 종유석과 석순을 나눠서 개수를 구하는 방식으로 접근해야 합니다. 

 

석순과 종유석을 담을 배열을 각각 선언하고 값을 넣어줍니다.

 

for(int i=0; i<n/2; i++) {
    int num1 = Integer.parseInt(br.readLine());
    int num2 = Integer.parseInt(br.readLine());
    down[i]=num1;
    up[i]=num2;
}

 

이제 이분 탐색을 위해 두 배열을 정렬해줍니다. 이분 탐색을 활용할 부분은 높이가 주어졌을 때 배열에 들어있는 값과 주어지는 높이를 이용해서 right 값을 구합니다. 이때 right값은 뿌셔지는 장애물 높이의 첫 번째 값이므로 그 값 이후는 모두 뿌셔 지게 됩니다. 따라서 arr.length-right를 하면 뿌셔지는 개수를 구할 수 있습니다. 

 

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

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

 

이제 h는 1~h까지 진행하여 가장 적게 뿌순 벽의 수와 그 개수를 구하면 됩니다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;
import java.util.*;

public class Main {

    static int result;
    static int [] up;
    static int [] down;
    static int n,h;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");

        n  = Integer.parseInt(s[0]);
        h  = Integer.parseInt(s[1]);

        up = new int[n/2];
        down = new int[n/2];
        for(int i=0; i<n/2; i++) {
            int num1 = Integer.parseInt(br.readLine());
            int num2 = Integer.parseInt(br.readLine());
            down[i]=num1;
            up[i]=num2;
        }

        int min = n;
        int count=0;

        Arrays.sort(up);
        Arrays.sort(down);


        for(int i=1; i<h+1; i++){
            int countWall = solve(0,n/2,i,down)+solve(0,n/2,h-i+1, up);

            if(min==countWall){
                count++;
                continue;
            }
            if(min>countWall){
                min=countWall;
                count=1;
            }
        }

        System.out.println(min +" "+count);

    }

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

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