[백준] 3020 개똥벌레

문제보기

분할정복 파트가 너무 약한것 같아서 관련 카테고리 문제만 집중적으로 풀고 있는데
자꾸 다른방법으로 풀고 앉아있다 ㅠㅠㅠㅠ
이 문제는 부분합을 이용해서 풀었다.
종유석을 길이를 인덱스로 해서 길이 종류별로 갯수를 top, bot배열에 넣어준 뒤
모든 높이값에 대해 부딪히는 종유석의 갯수를 세어서, 최솟값인 경우를 뱉으면 된다.
시간복잡도는 O(N+H)

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



class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };

     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int n = ip(st.nextToken());
    	int h = ip(st.nextToken());
    	int[] top = new int[h+1]; // 인덱스 = 높이, 높이별 갯수를 저장한다. 석순
    	int[] bot = new int[h+1]; // 종유석 
    	
    	for(int i = 0 ; i < n/2 ; i++) {
    		bot[ip(br.readLine())]++;
    		top[ip(br.readLine())]++;
    	}

    	int[] top_sum = new int[h+1]; // 부분합을 저장할 배열. top_sum[h]는 높이가 h이하인 석순의 갯수를 저장한다.
    	int[] bot_sum = new int[h+1]; // 종유석의 부분합 
		// 이렇게 부분합을 저장한다 
    	for(int i = 1 ; i <= h ; i++) {
    		top_sum[i] = top_sum[i-1] + top[i];
    		bot_sum[i] = bot_sum[i-1] + bot[i];
    	}
    	int min = n; // 최소 부딪힘 횟수 
    	int cnt = 0; // 최소 부딪힘 횟수가 발생하는 높이값의 갯수 
    	
    	for(int i = 1 ; i <= h ; i++) { // i = 높이
    		int obs = 0; // 부딪히는 종유석, 석순의 갯수를 저장할 변수 
		// 부딪히는 종유석의 갯수 = 전체 종유석갯수 - i-1이하인 종유석의 갯수
    		obs += bot_sum[h] - bot_sum[i-1];
		// 부딪히는 석순의 갯수 = 전체 석순의 갯수 - h-i이하인 석순의 갯수 
    		obs += top_sum[h] - top_sum[h-i]; 
			
    		if(obs < min) { // 만약 부딪히는 횟수가 최솟값보다 작다면 
    			min = obs; // 갱신해주고 
    			cnt = 1; // 처음이니깐 카운트는 1로 초기화
    		}else if(obs == min) { // 만약 같다면
    			cnt++; // 카운트만 올리기
    		}
    	}
    	System.out.println(min + " " + cnt);
     }
}