백준 3020 개똥벌레 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/3020

풀이는 다음과 같다.

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //길이, 열
        int H = Integer.parseInt(st.nextToken()); //높이, 행

        int[] s = new int[H+1]; //index 높이의 석순 수를 구한 다음, 낮을수록 누적합(높이 3일때 부러지면, 높이 1일때도 부러지니)
        //예를 들어, 높이 3의 석순이 3개면 s[3] = 3으로 기록 후,
        //3 높이로 지나갈때 부술 수 있는 종유석의 수는 s[3] + s[4] + ... + s[H] 이게 되므로 해당 내용을 구현.
        int[] j = new int[H+1];

        for(int i = 0 ; i < N ; i++) {
            int h = Integer.parseInt(br.readLine());
            if(i % 2 == 0) {
                s[h]++;
            }
            else {
                j[h]++;
            }
        }

        for(int i = H-1 ; i >= 1 ; i--) {
            s[i] += s[i+1]; //벌레가 i 높이로 갔을때 부수는 총 석순 수 (높이 i 이상의 석순 개수 누적합)
            j[i] += j[i+1]; //벌레가 H-i+1 높이로 갔을때 부수는 총 종유석 수
        }

        int[] broken = new int[H+1]; //index 높이로 갔을때 부수는 장애물의 총 수

        int min = N;
        for(int i = 1 ; i <= H ; i++) {
            int a = s[i] + j[H-i+1]; //높이 i 일때
            broken[i] = a;
            min = Math.min(a, min);
        }

        int nums = 0;
        for(int i = 1 ; i <= H ; i++) {
            if(broken[i] == min) nums++;
        }

        bw.write(String.valueOf(min + " " + nums));
        bw.flush();
        bw.close();


    }

    
}

누적합의 개념을 알고 있다면, 주석을 잘 읽으면 이해가 갈 내용이다.

for(int i = 0 ; i < N ; i++) {
            int h = Integer.parseInt(br.readLine());
            if(i % 2 == 0) {
                s[h]++;
            }
            else {
                j[h]++;
            }
        }

처음에 위 로직을 통해, 높이 h인 석순(s[])과 종유석(j[])의 수를 구한다.
(ex - s[2] = 5 -> 높이 2의 석순이 5개.)

for(int i = H-1 ; i >= 1 ; i--) {
            s[i] += s[i+1]; //벌레가 i 높이로 갔을때 부수는 총 석순 수 (높이 i 이상의 석순 개수 누적합)
            j[i] += j[i+1]; //벌레가 H-i+1 높이로 갔을때 부수는 총 종유석 수
        }

다음은 위 로직을 통해 누적합을 구한다.
예를 들어, 높이 3의 석순은 높이 1로 날때 부술 수 있으므로,

ㅣ
ㅣㅣ
ㅣㅣㅣ <= 여기! 높이 1로 날면, 높이 3 높이 2, 높이 1 석순이 부셔진다.

높이 1일때는 모든 모든 석순을 포함해야 한다.
즉,
s[i] = s[i] + s[i+1] + s[i+2] + .. + s[H] 가 되도록 누적합을 구한다.
이 로직을 마치면,
s[i] = 높이 i부터 높이 H까지의 석순의 총 개수 가 된다.

for(int i = 1 ; i <= H ; i++) {
            int a = s[i] + j[H-i+1]; //높이 i 일때
            broken[i] = a;
            min = Math.min(a, min);
        }

그다음은 i 높이로 날 때 부수는 장애물의 수를 구한다.
s[i] = i 높이로 날때의 석순 수이고,
j[H-i+1] = i 높이로 날때의 종유석 수이다.
종유석은 천장에서부터 자라므로 H-i+1을 사용했다.

나머지 로직은 broken을 통해 최솟값을 찾고,
해당 최솟값이 몇개있는지 구하는 로직이다.

주석에도 설명이 있으니, 잘 읽어보도록 하자!

처음엔,
누적합 사용에 눈이 멀어
int[][] arr 이런식으로 2중 배열으로 풀었다.
누적합 로직은 사용했지만,
메모리 제한이 128mb라서 틀려버리고 말았다.

(2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)
위 숫자 제한때문에 최고 20만 * 50만의
1000억의 배열이 탄생해버리기 때문이었다.

문제 풀때, 조금만 더 신경썼더라면 제대로 풀었을텐데 아쉽다.
시간복잡도 뿐만 아니라 메모리도 신경쓰자.