[JAVA] 백준 3020 개똥벌레

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

3020번: 개똥벌레

 

처음에는 단순히 이중 포문을 생각했고, 시간초과가 날 것 같아서 어떻게 풀어야 할까 고민을 했다..

누적합을 이용해야 하는 문제임을 알았음에도! (문제 유형 훔쳐봄) 어떻게 이용해야 할지 감이 오지 않았다... 

결국,, 블로그 참고 (요즘 혼자 해결하는 문제가 많이 적어진 것 같다 흑흑)

 

내가 처음 생각한 이중 포문은 높이 크기의 배열을 만들어서 높이가 h인 장애물이 들어온다 => 1~h 까지 반복문을 돌며 해당하는 배열의 값을 1씩 증가 시킨다. 하여 h에 해당하는 값을 찾는다!

누적합을 이용하게 되면, 높이가 h인 장애물에 대한 접근을 전체 장애물수에서 h-1 이하의 장애물의 개수를 빼어서 풀이!! (석순과 종유석의 배열을 다르게 한다)

 

따라서 h 이하의 장애물에 수에 대한 정보가 필요함! 

bot_sum[i]: i이하의 석순의 수

bot_sum[h]: h이하의 석순의 수 == 전체 석순의 개수

crush = bot_sum[H] - bot_sum[h-1] //h로 지나갔을 때 충돌하게 될 석순의 수

그렇다면 bot_sum[i]는 어떻게 구할까? 이때 누적합을 이용!

i-1 길이 이하의 석순의 수에서 i 길이의 석순을 합하면 i 이하의 석순의 수가 나온다

bot_sum[i] = bot_sum[i-1] + bot[i];

반대의 종유석은 전체 개수에서 H-i 이하의 종유석의 수를 빼주면 된다.

crush += bot_sum[H] - top_sum[H-i];

 

 

전체코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        bot = new int[H+1];
        top = new int[H+1];
        min = N; cnt = 0;

        for(int i=0;i<N/2;i++){
            bot[Integer.parseInt(br.readLine())]++;
            top[Integer.parseInt(br.readLine())]++;
        }

        process();

        System.out.println(min+" "+cnt);

    }

    static int N, H;
    static int[] bot, top;
    static int min, cnt;

    public static void process(){
        int[] bot_sum = new int[H+1]; // 높이가 h 이하인 석순의 수
        int[] top_sum = new int[H+1];

        for(int i=1;i<=H;i++){
            bot_sum[i] = bot_sum[i-1] + bot[i];
            top_sum[i] = top_sum[i-1] + top[i];
        }

        for(int i=1;i<H+1;i++){
            int crush = 0;

            crush += bot_sum[H] - bot_sum[i-1];
            crush += bot_sum[H] - top_sum[H-i];

            if(min>crush){
                cnt = 1;
                min = crush;
            } else if(min==crush){
                cnt++;
            }
        }
    }

}