백준 3020 JAVA : 개똥벌레

문제

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

3020번: 개똥벌레

 

풀이 예상

석순과 종유석의 높이를 받을 때마다 해당 높이의 카운트를 늘려주는 것은 최대 20만x50만 번의 작업이 이루어 지기 떄문에 다른 방법을 찾아야 겠다고 생각했다.

그래서 높이에 따른 개수를 저장하고, 누적합을 통해서 구간에 포함되는 장애물의 수를 구한다.

 

풀이방법 (접근 방법 & 시간복잡도)

예제 입력 1번을 예시로 들면

입력 받았을 때, bottom[] 배열은 이렇게 되어있다.

bottom[i]	0	1	2	3	4	5	6	7
개수	0	1	0	1	0	1	0	0

 

누적합을 사용해서 bottom[i] 의 값을 구간에 포함되는 장애물의 수로 바꾸면 아래와 같다.

bottom[i]	0	1	2	3	4	5	6	7
개수	0	3	2	2	1	1	0	0

 

마찬가지로 top[] 배열도 계산해서 결과를 구한다.

 

 

1. 아래(석순) 와 위(종유석) 의 개수를 저장한다.

2. 누적합을 사용해 해당 높이에서의 종유석 개수를 저장한다.

3. 아래(석순) 와 위(종유석) 의 합이 가장 작은 것을 찾아낸다.

 

 

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

public class Main {
    public static void main(String[] args) throws Exception{
        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 bottom[] = new int[H+1]; //bottom[i] : i 높이에서 석순 개수
        int top[] = new int[H+1]; //top[i] : i 높이에서 종유석 개수

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

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

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

        int minNum = Integer.MAX_VALUE;
        int result = 0;
        for (int i = 1; i <= H; i++) {
            int sum = bottom[i] + top[i];
            if(sum < minNum) {
                minNum = sum;
                result = 1;
            } else if (minNum == sum) {
                result +=1;
            }
        }
        System.out.println(minNum +" "+ result);
    }
}

 

결과