[백준 3020번 / 개똥벌레 / JAVA / 누적합]

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

3020번: 개똥벌레

 

문제 접근

List에 차례대로 모든 석순과 종유석을 저장하니 시간 초과가 떴다.

다른 방법을 참고하니 모든 석순과 종유석을 저장하는 게 아니라 각 높이 별로 석순과 종유석이 몇 개 있는지 카운팅해서 사용하는 게 시간을 단축해주는 방법이더라 → List 대신 배열로 인덱스 마다 해당 높이의 석순, 종유석 갯수 체크

이후 각 구간 별로 이전까지의 석순과 종유석을 누적 합산

높이만큼 반복문을 돌면서 (전체 - 현재 구간의 이전 구간 누적 합)을 빼주는 식으로 현재 구간에서 몇 개의 석순과 종유석에 부딪히는지 알 수 있다.

 

++ 풀이를 봐도 얼추 이해는 되나 뭔가 확 와닿진 않더라 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int depth = Integer.parseInt(st.nextToken()); // 크기는 항상 짝수
		int height = Integer.parseInt(st.nextToken()); // 높이
				
		int[] bottom = new int[height+1]; // 높이별 석순 개수 배열
		int[] top = new int[height+2]; // 높이별 종유석 개수 배열
		
		for(int i=0; i<depth/2; i++) {
			int b = Integer.parseInt(br.readLine());
			int t = height - Integer.parseInt(br.readLine())+1;
			
			bottom[b]++;
			top[t]++;
		}
		
		// 석순 누적 계산
		for(int i = 1; i <= height; i ++) bottom[i] = bottom[i] + bottom[i-1];
		
		// 종유석 누적 계산
		for(int i = height; i >= 1; i--) top[i] = top[i] + top[i+1];	
		
		int min = depth;
		int count = 0;
		
		for(int i = 1; i <= height; i++) { // 구간별 충돌 횟수
			int cal = (bottom[height] - bottom[i-1]) + (top[1] - top[i+1]);
			
			if(cal < min) {
				min = cal;
				count = 1;
			}
			else if(cal == min) count++;
		}
		
		System.out.println(min + " " + count);
	}
}