[백준] 3020 개똥벌레 - JAVA

출처 - 백준 알고리즘

3020번: 개똥벌레

---

 

알고리즘

N이 최대 200,000이고 H가 최대 500,000 이기 때문에 모든 경우에 대해 하나하나 탐색하게 되면 시간초과/메모리 초과가 발생한다. 

 

입력을 받으면서 특정 높이에서 만날 수 있는 석순 / 종유석의 갯수를 따로 각각 저장하였다. 이후, 높이를 역순으로 하여 해당 높이보다 더 작은 높이에 모두 누적으로 합해주었다. 예를 들어 장애물의 길이가 7이라면, 1~7까지의 모든 높이에서 해당 장애물을 만날 수 있기 때문이다. 

(즉, 높이가 n인 장애물은 1~n의 높이에서 모두 만날 수 있기 때문에 역순으로 저장)

 

이후, 특정 높이에서 만날 수 있는 장애물의 갯수 = 석순의 갯수 + 종유석의 갯수 

장애물 갯수를 계산하며 동시에 최솟값 + 갯수 구하기 

 

/**

ex) 예제입력1

up[1]=1  up[3]=1  up[5]=1

 

i= 7 ~ 2
i=7, up[6]=up[7]+up[6]= 0
i=6, up[5]=up[6]+up[5]= 1 
i=5, up[4]=up[5]+up[4]= 1
i=4, up[3]=up[4]+up[3]=2
i=3, up[2]=up[3]+up[2]=2
i=2, up[1]=up[2]+up[1]=3

up[1]=3 down[1]=3
up[2]=2 down[2]=2
up[3]=2 down[3]=2
up[4]=1 down[4]=1
up[5]=1 down[5]=1
up[6]=0 down[6]=0
up[7]=0 down[7]=0

**/

---

 

소스 코드

import java.util.*;
import java.io.*;

public class Solution_BaekJoon_3020 {
	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[] block = new int[H+1]; //각 높이에서 장애물의 갯수  
		int[] up = new int[H+1]; //종유석(↓) 위에서부터 특정높이에 몇개걸리는지
		int[] down = new int[H+1]; //석순(↑) 아래서부터 특정높이에 몇개걸리는지 
		
		//석순-종유석 이 번갈아가면서 나온다
		for(int i=0; i<N/2; i++) {
			down[Integer.parseInt(br.readLine())]++;
			up[Integer.parseInt(br.readLine())]++;
		}
		
		for(int i=H; i>1; i--) {
			up[i-1] += up[i]; 
			down[i-1] +=down[i]; 
		}

		int min=Integer.MAX_VALUE;
		int min_cnt=0; 
		for(int i=1; i<=H; i++) {
			block[i] = up[i]+down[H+1-i];
			if(min ==block[i]) {
				min_cnt++;
			}
			if(min>block[i]) {
				min=block[i]; 
				min_cnt=1; 
			}
		}
		System.out.println(min+" "+min_cnt);
	}//end of main
}//end of class