[백준] #3020. 개똥 벌레 (골드 5)

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

import java.io.*;
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[] up = new int[h+1];  //석순
		int[] down = new int[h+1];  //종유석
		for (int i = 0; i < n / 2; i++) {
			up[Integer.parseInt(br.readLine())]++;  //해당 석순의 높이 인덱스에 개수 추가
			down[Integer.parseInt(br.readLine())]++;  //해당 종유석의 높이 인덱스에 개수 추가
		}


		int[] upSum = new int[h+1];  // 높이가 i 이하인 석순의 수 저장할 배열
		int[] downSum = new int[h+1];  // 높이가 i 이하인 종유석의 수 저장할 배열

		// 누적합 구하기
		for(int i = 1; i <= h; i++){
			upSum[i] = upSum[i-1] + up[i];  // 높이가 i 이하인 석순의 수 저장
			downSum[i] = downSum[i-1] + down[i];  // 높이가 i 이하인 종유석의 수 저장
		}


		int min = n;  //장애물의 최솟값
		int cnt = 0;  //장애물이 최솟값인 구간의 수

		for(int i = 1; i <= h; i++) {  // 높이
			int crush = 0;

			crush += upSum[h] - upSum[i - 1];          //높이 i 이상 h 이하의 석순의 개수 (1이상 5이하) (2이상 5이하) (3이상 5이하) (4이상 5이하) (5이상 5이하)
			crush += downSum[h] - downSum[h - i];  //높이 h-i+1 이상 h 이하의 종유석 개수 (5이상 5이하) (4이상 5이하) (3이상 5이하) (2이상 5이하) (1이상 5이하)

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

		System.out.print(min + " " + cnt);
	}
}

 

 

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

public class Main {
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken()); // 동굴 길이
        int h = Integer.parseInt(st.nextToken()); // 동굴 높이

        int[] s = new int[h+1];  // 석순
        int[] j = new int[h+1]; // 종유석

        for(int i=0;i<n/2;i++)
        {
            int sh = Integer.parseInt(bf.readLine()); // 1 3 5
            int jh = Integer.parseInt(bf.readLine()); // 5 3 1
            s[sh]++; // 해당 배열 수 증가 -> 1 0 1 0 1 0 0
            j[jh]++; // 해당 배열 수 증가 -> 1 0 1 0 1 0 0
        }

        // s[i] = s[i+1] + A[i]
        // s[i] = s[i+1] + s[i]
        for(int i=h;i>0;i--)
        {
            s[i-1] = s[i]+s[i-1]; // 3 2 2 1 1 0 0 -> 1구간 석순 3개 깨짐, 2구간 석순 2개 깨짐
            j[i-1] = j[i]+j[i-1]; // 3 2 2 1 1 0 0 ->
        }
        int min = Integer.MAX_VALUE;
        int cnt = 0;

        for(int i=1;i<=h;i++)
        {
            int tmp = s[i]+j[h+1-i]; //s[1] + j[7], s[2]+h[6]
            // 3 2 3 2 3 2 3
            if(tmp<min)
            {
                min = tmp;
                cnt = 1;
            }
            else if(tmp == min)
            {
                cnt++;
            }
        }
        System.out.println(min+" "+cnt);
    }
}