[백준] 3020번: 개똥벌레 - java

 

 

아이디어

동굴의 길이 N만큼 장애물 배열을 만들고, 구간별 파괴해야하는 장애물의 수를 구한다면 (N크기 : 20만 X H크기 : 50만) 으로 시간초과 가 날 것이다. 

 

따라서 장애물 배열을 구간의 개수인 H만큼 만들고, N만큼의 입력에 대해 장애물의 길이에 해당하는 인덱스에 갯수를 카운트 해주었다. => 해당 길이의 장애물이 몇 개 있는지를 카운트한다.

=> top[1] = 0      top[2] = 2       top[3] = 3      top[4] = 0       top[5] = 2

     down[1] = 1   down[2] = 1   down[3] = 4   down[4] = 1   down[5] = 0

 

 

 

만약 길이가 1,2,3,4 인 종유석이 4개 있다고 가정하고, 아래에서부터 2번째 구간을 지나간다고 생각해보자.

2번째 구간을 지나간다면 파괴해야 하는 장애물은, 높이가 2,3,4인 장애물로 3개다.

3번째 구간을 지나간다면 높이가 3,4인 장애물로 2개

4번째 구간을 지나간다면 높이가 4인 장애물로 1개를 파괴해야 할 것이다.

=> 누적합의 개념이다.

 

 

=> 따라서 h높이의 구간을 지날 때 파괴하는 장애물의 수를 누적합으로 구할 수 있다.

그러기 위해서는 N개의 장애물에 대해, 해당 길이의 장애물이 몇 개 있는지를 카운트해야한다.

ex) top[1]++; // 길이가 1인 석순 개수 1카운트

 

 

 

즉, 구현순서는 다음과 같다.

 

1. 석순와 종유석은 각각 따로 입력을 받는다 => O(N)

    종유셕은 위에서부터 떨어지는 장애물, 석순은 아래서부터 올라오는 장애물로, 두 장애물의 배열을 따로 두었다.

 

2. 구간 1부터 h까지 누적합을 구한다. => 누적합 : 길이가 i인 구간을 지날 때 파괴해야 하는 장애물 수 

     => O(H)

 

3. 종유석은 구간이 1~h 순으로, 석유는 h~1 순으로 되어 있음을 명심하고, 해당 구간에서의 석순 누적합 수 + 종유석 누적합 수를 최종적으로 구한다.

 

=> 최종적으로 O(N+H) 시간에 구할 수 있음!

 

 

 

장애물 길이별 카운트

top[size], down[size] => size 크기를 가진 종유석,석순의 개수

 

누적합 구하기

top[i], down[i] => i구간에 존재하는  종유석,석순의 개수
길이가 i인 장애물을 파괴한다면, 항상 i보다 긴 길이의 장애물도 파괴해야 한다.

=> 길이가 긴 장애물부터 역순으로 누적합을 구한다. 

* 길이가 i인 구간을 지날 때는, 길이가 i이상인 모든 장애물을 파괴해야 한다.

ex) 구간 1을 지날 때는 모든 종유석 장애물을 파괴해야 함.

 

i 구간의 석순+종유석 장애물 수 구하기

석순  : down[i]

종유석 : top[H-i+1]  

 

전체코드

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb;
	static StringTokenizer st;
	static int N, H, size, val, min_val=Integer.MAX_VALUE, min_cnt, top[], down[];

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		top = new int[H+1];
		down = new int[H+1];

		/**
		 * top[size], down[size] => size크기를 가진 석순, 종유석의 개수
		 */
		for (int i = 1; i <= N; i++) { 
			size = Integer.parseInt(br.readLine());
			if (i % 2 == 0) { // 짝수번째는 종유석. 장애물이 위에서부터 내려온다.
				top[size]++;
			} else { // 짝수번째는 석순. 장애물이 밑에서부터 올라온다.
				down[size]++;
			}
		}
		
		/**
		 * 구간합 구하기
		 * top[i], down[i] => i 구간에 존재하는 장애물의 개수
		 * i 장애물을 지나간다면, 항상 i보다 큰 사이즈의 장애물도 지나가야 한다.
		 */
		for(int i=H-1; i>=1; i--) {
			top[i] += top[i+1];
			down[i] += down[i+1];
		}
		
		/**
		 * 장애물이 최소인 구간 구하기
		 * i번째 구간의 장애물 개수 => top[H-i+1] + down[i] 
		 */
		 for(int i=1; i<=H; i++) {
			 val = top[H-i+1] + down[i];
			 if (val < min_val) {
				 min_val = val;
				 min_cnt = 1;
			 } else if (val==min_val)
				 min_cnt++;
		 }
		
		 System.out.println(min_val + " " + min_cnt);
	}
}