이번에 풀어본 문제는
백준 3020번 개똥벌레 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int [] bottom,top;
    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());

        bottom = new int[h+1];
        top = new int[h+1];

        for(int i = 0; i < n; ++i)
        {
            int height = Integer.parseInt(br.readLine());

            if(i % 2 == 0) bottom[height]++;
            else top[height]++;
        }

        for(int i = h-1; i > 0; --i)
        {
            bottom[i] += bottom[i+1];
            top[i] += top[i+1];
        }

        int min = Integer.MAX_VALUE;
        int cnt = 0;
        for(int i = 1; i <= h; ++i)
        {
            int total = bottom[i] + top[h-i+1];

            if(min > total)
            {
                min = total;
                cnt = 1;
            }
            else if(min == total) cnt++;
        }
        System.out.printf("%d %d",min,cnt);
    }
}

📝 풀이

높이를 입력받음과 동시에 석순(bottom),종유석(top)의 해당 높이값을 1씩 카운트 해주고,자신보다 낮은 높이일 경우 무조건 자신을 부수고 지나가야 하므로 높은곳에서부터 역으로 카운트값을 증가시켜줍니다.
마지막으로 높이 1부터 total값을 구해 최솟값을 구해주며, 최솟값과 같을경우 cnt를 증가시켜 중복값까지 찾아줄 수 있습니다.

📜 후기

코딩테스트때 효율성 통과 못한것이 분해서 누적합 알고리즘 문제만 풀고있는데, 비슷한 유형을 찾기가 쉽지 않네요 ㅎㅎ.. 후기글을 찾아보면 비슷한 유형을 찾을 수 있을까 싶네요! 내일은 다른 문제도 좀 풀어봐야겠습니다,,