[JAVA] 백준, 3020번 개똥벌레

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

해설

석순(bottom)의 경우 입력받은 값 그대로 저장하면 되지만, 종유석(top)의 경우 전체 높이에서 입력받은 크기를 빼고 저장한다.

각 bottom, top 인덱스의 의미는 장애물의 크기를 의미한다.

 

각 누적합 인덱스에는 구간에 따른 장애물을 부실 수 있는 개수를 저장한다.

• bottom : 만약 구간이 1이라면 bottom의 1, 3, 5번째 장애물을 모두 부실 수 있다. 
• top : 만약 구간이 4라면 top의 2번째 장애물만 부실 수 있다.

코드

import java.io.*;
import java.util.*;

public class Main {

    static int N, H;
    static int[] top;
    static int[] bottom;
    static int res, cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        top = new int[H + 1];
        bottom = new int[H + 1];

        for (int i = 0; i < N / 2; i++) {
            int b = Integer.parseInt(br.readLine());
            int t = H - Integer.parseInt(br.readLine());
            bottom[b]++;
            top[t]++;
        }

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

        res = Integer.MAX_VALUE;
        solution();
    }

    static void solution() {
        for (int i = 1; i <= H; i++) {
            int result = bottom[H] - bottom[i - 1] + top[i - 1];

            if (result < res) {
                res = result;
                cnt = 1;
            } else if (result == res) {
                cnt++;
            }
        }

        System.out.println(res + " " + cnt);
    }
}