2 분 소요

문제

문제 바로가기

입력

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

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

출력

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

접근방법

이진탐색, 누적합 2가지 방식으로 풀 수 있는 문제다.

1. 이진탐색

  먼저 이진탐색을 하려면 정렬을 해야 한다. 장애물의 크기를 입력받은 down[]과 up[]을 각각 오름차순으로 정렬해준다. 그리고 1부터 H까지 높이를 기준으로 이진탐색을 수행해준다. 여기서 장애물의 크기가 right 이상이면 파괴해야하는 장애물을 의미한다. 따라서, arr.length - right를 통해 파괴되는 장애물의 수를 구할 수 있다. 주의해야 할 점은 석순과 종유석은 위아래가 반대라서 석순의 높이가 i일 때 종유석의 높이는 H-i+1 이다.

2. 누적합

  장애물의 크기를 입력받아 down[]과 up[]에 각각 장애물 크기의 개수를 카운트해준다. 그리고 높이가 높은 곳에서 낮은 곳으로 값을 누적해서 저장해준다. 그 이유는 높이가 1인 곳을 지나갈 때, 높이가 1이상인 장애물은 모두 파괴되기 때문이다. 따라서, 누적해서 값이 저장된 배열을 이용해 파괴되는 장애물의 수를 구할 수 있다.



풀이


이진탐색

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

public class Main {
    public static void main(String[] args) throws IOException {
        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[N/2];
        int[] up = new int[N/2];

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

        int min = N;
        int count = 0;

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

        for(int i = 1; i <= H; i++) {
            int cnt = binarySearch(0, N/2, down, i) + binarySearch(0, N/2, up, H-i+1);
            if(min == cnt) {
                count++;
            }
            else if(min > cnt) {
                min = cnt;
                count = 1;
            }
        }

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

    public static int binarySearch(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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        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++) {
            down[Integer.parseInt(br.readLine())]++;
            up[Integer.parseInt(br.readLine())]++;
        }

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

        int min = N;
        int count = 0;

        for(int i = 1; i <= H; i++) {
            int cnt = down[i] + up[H-i+1];
            if(cnt == min) {
                count++;
            }
            else if(min > cnt) {
                min = cnt;
                count = 1;
            }
        }

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

댓글남기기

참고