백준 3020 개똥벌레 Java [누적합]

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

3020번: 개똥벌레

 

동굴에 종유석과 석순을 하나하나 만들어주면 예제가 모두 최대값인 50만 x 20만번으로 시간이 부족하다

그래서 종유석과 석순 배열을 동굴의 높이 크기로 만들어

1이 나오면 0번 인덱스에 1을 추가하고

n이 나오면 n-1번 인덱스에 1을 추가하는 방식으로 갯수를 카운트해줬다

동굴 배열도 높이 크기로 만들고 0번 인덱스를 최상단으로 하여

종유석 전체 갯수 N/2개를 동굴 0번 인덱스에 더하고 종유석 전체 갯수에서 종유석 0번 인덱스 갯수만큼 뺀다

석순 N - 1번 인덱스를 석순 갯수에 더한 후 동굴 0번 인덱스에 더해준다

해당 인덱스가 최소값인지 확인하고 최소값보다 작으면 갱신하고, 같으면 카운트 1 더해준다

이 방식으로 풀면 시간복잡도 O(H)로 풀이할 수 있다

 

import java.io.*;
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[] under = new int[H];
        int[] over = new int[H];
        int[] cave = new int[H];
        int overCount = N/2, underCount = 0, destroy = N, count = 0;
        for (int n = 0; n < N; n++) {
            int now = Integer.parseInt(br.readLine()) - 1;
            if (n % 2 == 0) under[now]++;
            else over[now]++;
        }
        for (int h = 0; h < H; h++) {
            underCount += under[H - 1 - h];
            cave[h] += overCount + underCount;
            overCount -= over[h];
            if (cave[h] < destroy) {
                destroy = cave[h];
                count = 1;
            } else if (cave[h] == destroy) count++;
        }
        System.out.println(destroy + " " + count);
    }
}