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

www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

1. 문제 설명

 

개똥벌레가 석순과 종유석으로 가득 찬 동굴에 들어갔다. 동굴의 길이는 N미터이고 높이는 H미터일 때 첫 번째 장애물은 항상 석순이고, 그다음부터는 종유석과 석순이 번갈아가면서 등장한다. 개똥벌레는 일직선으로 장애물을 파괴하면서 지나간다고 하였을 때, 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 문제이다.

 

 

2. 풀이

 

동굴의 길이 N (2<=N<=200,000)과 높이 H(2 <=H <=500,000)의 크기가 크므로 단순하게 코드를 짜면 시간 초과를 받을 수 있다.

 

장애물의 높이를 석순과 종유석으로 나누어서 입력을 받은 후, 높이의 누적합을 구한다. 

 

누적합을 통해서 높이가 X일때 몇 개의 장애물을 거치는지 알 수 있다.

(석순의 높이가 3이면 높이가 1,2,3일때 모두 석순을 파괴한다...!)

 

최종적으로 높이가 X일때 석순과 종유석의 장애물을 합해 총 몇 개를 파괴하는지 구한 뒤 최솟값을 구하면 된다.

 

3. 코드

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N, H;
        int answer = 500000, num = 0;

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

        N = Integer.parseInt(input.nextToken());
        H = Integer.parseInt(input.nextToken());

        int dp_down[] = new int[H + 1];
        int dp_up[] = new int[H + 1];

        for (int x = 0; x < N; x++) {
            int height = Integer.parseInt(br.readLine());

            // 아래부터
            if (x % 2 == 0) {
                dp_down[height]++;
            } else {
                dp_up[height]++;
            }
        }

        for (int x = H-1; x > 0; x--) {
            dp_down[x] += dp_down[x + 1];
            dp_up[x] += dp_up[x + 1];
        }

        for (int x = 1; x <= H; x++) {
            int now = dp_down[x] + dp_up[H + 1 - x];

            if (now < answer) {
                answer = now;
                num = 1;
            } else if ( now== answer) {
                num++;
            }
        }

        System.out.println(answer + " " + num);

    }


}