[BOJ] 3020. 개똥벌레

[작성일]

• 2022-02-15

[분류]

• 누적합
  
  
  

[문제링크]

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

[요구사항]

• 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하라.
  
  
  

[풀이]

높이 1부터 H까지 개똥벌레를 대조하면서 비교하기 위해서는 석순과 종유석을 높이에 따라서 개수를 저장해두어야 한다고 생각했다. 높이에 따라서 저장하기 위해서는 누적합을 사용해서 저장하였다.

1) bot배열과 top배열을 각각 두고 높이에 따라서 +1 씩 해주며 입력받는다.

2) 누적합을 구해준다.

3) 개똥벌레 높이를 1~H까지 두고 그 때 부딪히는 bot과 top의 합을 누적합 배열을 이용해 구한다.

[코드]

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


public class Main {
    static int N, H;
    static int[] bot;
    static int[] top;
    static int[] botSum;
    static int[] topSum;

    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());

        // height에 따라 더해주기
        bot = new int[H + 1];
        top = new int[H + 1];
        for (int i = 0; i < N / 2; i++) {
            bot[Integer.parseInt(br.readLine())]++;
            top[Integer.parseInt(br.readLine())]++;
        }

        // 누적합 구해주기
        botSum = new int[H + 1];
        topSum = new int[H + 1];
        botSum[H] = bot[H];
        topSum[H] = top[H];
        for (int i = H - 1; i > 0; i--) {
            botSum[i] = botSum[i + 1] + bot[i];
            topSum[i] = topSum[i + 1] + top[i];
        }

        int min = Integer.MAX_VALUE;
        int minCnt = 0;
        for (int i = 1; i <= H; i++) {
            int value = botSum[i] + topSum[H - i + 1];
            if(min > value) {
                min = value;
                minCnt = 1;
            } else if(min == value) {
                minCnt++;
            }
        }

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

[느낀점]

꽤 어려웠는데 누적합 문제를 좀 더 많이 풀어봐야겠다.