[BOJ] 백준 3020. 개똥벌레

문제

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

 

 

---

풀이

 누적합을 이용해 해결한 문제입니다. 입력값이 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 으로 주어지기 때문에, 이중 for문을 돌면 바로 시간 초과에 걸리게 됩니다.

 문제 상황을 위처럼 그림으로 나타내볼 수 있었습니다. 각 높이별로 파괴해야하는 장애물의 개수을 표시한 것입니다. 

저 개수를 어떻게 구해야할지 생각해보다가 우선 석순과 종유석 배열을 각각 나누어야겠다고 생각했습니다.

 

 

 

 그래서 우선 입력을 석순과 종유석(bottom[], up[])배열에 나누어서 받았습니다.

이 때, 주어지는 입력 값인 장애물의 크기는  bottom[], up[] 배열의 인덱스로 입력받아, 해당하는 인덱스 배열의 값을 +1 해줍니다.

 

그러면 우선,  그림처럼 나오게 됩니다.

이 때 한번에 높이별 합을 구하지 않는 것은 이중 for문을 돌면 시간초과가 발생하기 때문입니다.

 

이제 이 값을 통해 누적합을 구할 수 있습니다. 한 번의 for문을 돌면서 이전 인덱스를 누적합 시키면 됩니다.

bottomSum[i+1] += bottomSum[i];

 식을 통해 누적합을 구한 그림은 위와 같고 up[] 배열도 마찬가지 과정을 진행해주면 됩니다.

 

그리고 두 배열을 합쳐, 높이별 장애물 개수를 구할 수 있습니다.

 

 

 

아래는 소스 코드입니다.

 

 

---

소스 코드

import java.util.Arrays;
import java.util.Scanner;

public class B3020_개똥벌레 {
    static int[] bottomSum;
    static int[] upSum;
    static int[] prefixSum;
    static int N,H;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        H = sc.nextInt();
        bottomSum = new int[H];
        upSum = new int[H];
        prefixSum = new int[H];

        for(int i = 0;i<N/2;i++){
            int b = sc.nextInt()-1;
            int u = sc.nextInt()-1;
            bottomSum[b]++;
            upSum[H-1-u]++;
        }

        for(int i =0;i<H-1;i++){
            upSum[i+1] += upSum[i];
            bottomSum[H-(i+2)] += bottomSum[H-(i+1)];
        }
        
        for(int i =0;i<H;i++){
            prefixSum[i] = upSum[i]+bottomSum[i];
        }
        Arrays.sort(prefixSum);

        int cnt = 0;
        for(int i = 0;i<H;i++){
            if(prefixSum[0]==prefixSum[i]) cnt++;
            else break;
        }
        System.out.println(prefixSum[0]+" "+cnt);
    }
}