[BAEKJOON 백준] 3020 개똥벌레 (JAVA)

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

3020번: 개똥벌레

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

예제 입력 1 복사

6 7
1
5
3
3
5
1

예제 출력 1 복사

2 3

예제 입력 2 복사

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력 2 복사

7 2

누적합 풀이

이는 down[]과 up[]에 각 장애물 높이를 카운트해준다. 그런 다음 해당 정보를 누적합으로 저장한다. 

• down[장애물 높이]++;
• up[h-장애물 높이+1]++;

// 누적합 
for(int i=1; i<=h; i++) {
	down[i] += down[i-1];
}

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

 

누적합에 대한 정보를 가지고 해당 구간에 존재하는 장애물의 수를 구해서 탐색해주면 된다.

• i구간에 해당하는 장애물 갯수 구하기
  • down : (down 장애물 최대 갯수)  -  이전 장애물 갯수(i-1)
  • up : (up 장애물 최대 갯수) - 이전 장애물 갯수(i+1)
  • int dif = (down[h]-down[i-1]) + (up[1]-up[i+1]);

 

탐색과정에 대한 예시를 돌려보면 다음과 같다. 이진탐색보다 구상하기 어렵지만 더 효율적인 탐색으로 답을 얻어낼 수 있다.

 

누적합 풀이

 

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

public class Main {

	static int N; // 동굴의 길이
	static int H; // 동굴의 높이
	static int[] top;// 석순
	static int[] bot;// 종유석
	static int min; // 파괴하는 장애물의 최솟값
	static int cnt; // min에 해당되는 구간의 수

	public static void main(String[] args) throws IOException {
		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; // min에 해당되는 구간의 수

		for (int i = 0; i < N / 2; i++) {
			bot[Integer.parseInt(br.readLine())]++; // 석순(bot)
			top[Integer.parseInt(br.readLine())]++; // 종유석(top)
		} // End of input

		process();

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

	}

	private static void process() {

		int[] bot_sum = new int[H + 1]; // 높이가 h이하인 석순의 갯수
		int[] top_sum = new int[H + 1]; // 높이가 h이하인 종유석의 갯수

		// 누적합 계산
		for (int i = 1; i < H + 1; i++) {
			top_sum[i] = top_sum[i - 1] + top[i];
			bot_sum[i] = bot_sum[i - 1] + bot[i];
		}

		for (int i = 1; i < H + 1; i++) {
			int crush = 0; // 부딪히는 개수

			// 부딪히는 석순의 갯수 = 전체 석순의 갯수 - (h-i)이하인 석순의 갯수
			crush += bot_sum[H] - bot_sum[i - 1];
			// 부딪히는 종유석의 갯수 = 전체 종유석갯수 - (i-1)이하인 종유석의 갯수
			crush += top_sum[H] - top_sum[H - i];

			// 최솟값 && 개수 위한 조건문
			if (min > crush) {
				min = crush;
				cnt = 1;
			} else if (min == crush) {
				cnt++;
			}
		}

	}

}