3020 개똥벌레 (Java)

개똥벌레

문제

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

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

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

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

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

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

입력

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

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

출력

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

풀이

석순과 종유석에 대해서 특정 높이에서 파괴되는 장애물의 수를 구한다.
이를 단순하게 구현하면 특정 높이에서 그보다 아래 혹은 위에 있는 모든 석순, 종유석을 찾으므로 O(N^2)의 시간이 걸린다.
이 문제에서 위의 방식을 사용한다면 200,000 * 500,000^2로 시간초과에 걸린다.
그러므로 시간을 줄이기 위해 누적합 알고리즘을 사용한다.

우선 높이 정보를 입력받는다.
이해를 쉽게 하기 위해 석순의 경우만 고려하면 다음과 같다.

높이 정보를 저장하기 위한 배열 int[] bot = new int[h+1];을 선언한다.
1의 높이를 입력받으면 bot[1]++을 통해 개수를 저장한다.
2의 높이를 입력받으면 bot[2]++을 통해 개수를 저장한다.
이 개수는 특정 높이를 선택하여 지나갈 때 뚫어야 하는 개수이다.
그런데 뭔가 이상하지 않은가??
높이 1을 지나갈 때 1을 뚫는 것 뿐만 아니라 2도 뚫어야 한다.
그러나 우리가 저장한 정보에는 1만 뚫는 갯수를 저장했다.
이를 위해서 누적합 알고리즘을 사용한다.
석순은 아래에서 위로 자라므로 높이가 n이라면 1~n까지 높이에서 지나갈때 모두 뚫고 지나가야 한다.
즉 뚫고 지나가는 갯수 bot[n-1] 은 bot[n]을 포함해야 한다.
이를 구현하면 다음과 같다.

for (int i = h - 1; i >0; i--) {
            bot[i] += bot[i + 1];
        }

이러한 방식을 종유석에도 적용하여 토탈합을 구한 후 답을 도출한다.

코드

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

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[] top = new int[h + 1];
        int[] bot = new int[h + 1];

        for (int i = 0; i < n / 2; i++) {
            int botSize = Integer.parseInt(br.readLine());
            int topSize = Integer.parseInt(br.readLine());
            topSize = h - topSize + 1;
            bot[botSize]++;
            top[topSize]++;
        }

        // 누적합
        for (int i = h - 1; i >0; i--) {
            bot[i] += bot[i + 1];
        }

        for (int i = 1; i <= h; i++) {
            top[i] += top[i - 1];
        }

        int[] total = new int[h + 1];
        for (int i = 0; i < h + 1; i++) {
            total[i] = bot[i] + top[i];
        }

        // 0번째 인덱스 처리
        total[0] = 200001;

        Arrays.sort(total);
        int dupliCnt = 0;

        for (int i = 0; i < total.length; i++) {
            if (total[i] != total[0]) {
                break;
            }
            dupliCnt++;
        }

        System.out.println(total[0] + " " + dupliCnt);
    }
}