[백준/3020] 개똥벌레 - JAVA

📌 문제

알고리즘 분류 : 누적합
난이도 : 골드5
출처 : 백준 - 개똥벌레

🦧 문제 풀이 접근

모든 석순의 시작되는 부분에 +1, 끝나는 부분에 -1을 해준 후 누적해가면서 해당 위치에 석순의 갯수를 찾는다.

💻 code

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

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 N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
        int[] dp = new int[H+2];
        for(int i=0;i<N;i++) {
            int obstacle = Integer.parseInt(br.readLine());
            if(i%2==0) {
                dp[1]++;
                dp[obstacle+1]--;
            }
            else {
                dp[H-obstacle+1]++;
            }
        }
        int min=Integer.MAX_VALUE;
        int minCount=0;
        for(int i=1;i<=H;i++) {
            dp[i]+=dp[i-1];
            if(dp[i]<min) {
                min=dp[i];
                minCount=1;
            }
            else if(dp[i]==min) {
                minCount++;
            }
        }
        System.out.println(min+" "+minCount);
    }
}

🥇 결과

🎓 느낀점

누적합에 자주 보이는 유형이다. 이중 포문을 이용해 석순의 갯수를 체크하면 시간초과가 나오니 조심하자.