[BaekJoon] 3020 개똥벌레

1.  문제 링크

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

2.  문제

요약

• 개똥벌레 한 마리가 석순과 종유석으로 가득찬 항상 짝수인 N미터의 길이, H미터 높이의 동굴에 들어갑니다.
• 동굴에는 첫 번째 장애물(석순, 종유석)은 항상 석순이고, 그 다음부터는 종유석과 석순이 번갈아가며 등장합니다.
• 개똥벌레는 장애물을 만나면 피하지 않고 파괴하며 가는데 동굴의 크기, 높이, 모든 장애물의 크기가 주어졌을 때 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 항상 짝수이며 2보다 크거나 같고 200,000보다 작거나 같은 동굴의 길이 N과 2보다 크거나 같고 500,000보다 작거나 같은 동굴의 높이 H가 주어지고 두 번째 줄부터 N개의 줄에는 H보다 작은 양수인 장애물의 크기가 순서대로 주어집니다.
• 출력: 첫 번째 줄에 파괴해야 할 장애물의 최솟값과 그러한 구간의 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	public int getObstacleNum(int start, int end, int height, int[] obstacle) {
		while(start < end) {
			int mid = (start + end) / 2;
			if(obstacle[mid] >= height) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		return obstacle.length - end;
	}
	
	public int[] getMinObstacle(int len, int height, int[] obstacle_len) {
		int[] stalagmite = new int[len / 2];
		int[] stalactite = new int[len / 2];
		int s1 = 0;
		int s2 = 0;
		for(int i = 0; i < obstacle_len.length; i++) {
			if(i % 2 == 0) {
				stalagmite[s1] = obstacle_len[i];
				s1++;
			} else {
				stalactite[s2] = obstacle_len[i];
				s2++;
			}
		}
		Arrays.sort(stalagmite);
		Arrays.sort(stalactite);
		int min = len;
		int count = 0;
		for(int i = 1; i <= height; i++) {
			int obstacle = getObstacleNum(0, len / 2, i, stalagmite) + getObstacleNum(0, len / 2, height - i + 1, stalactite);
			if(min == obstacle) {
				count++;
				continue;
			}
			if(min > obstacle) {
				min = obstacle;
				count = 1;
			}
		}
		int[] result = new int[2];
		result[0] = min;
		result[1] = count;
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int len = Integer.parseInt(input[0]);
		int height = Integer.parseInt(input[1]);
		int[] obstacle_len = new int[len];
		for(int i = 0; i < len; i++) {
			obstacle_len[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		int[] result = m.getMinObstacle(len, height, obstacle_len);
		for(int i = 0; i < result.length; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 이진 탐색을 이용하여 해결할 수 있는 문제입니다.
• 개똥벌레가 지나갈 수 있는 곳들 모두에서 이진 탐색을 통해 파괴해야 할 장애물의 개수를 구하고 구한 파괴할 장애물의 개수가 이전에 구해왔던 장애물의 개수 중 최소의 개수보다 작다면 최소 개수를 변경하고 최소 개수와 같은 위치의 개수를 구합니다.
• 석순은 아래에서 위로, 종유석은 위에서 아래로 진행하는 장애물이기 때문에 해당 위치에서 장애물을 파괴해야 하는지 판단하는 방법이 다르므로 두 종류를 분류하여 파괴할 장애물의 개수 파악을 진행해야 합니다.
• 파괴해야 하는 장애물의 최소의 개수를 구해야 하므로 이진 탐색 중 lower bound를 이용합니다.

1. 장애물들의 높이를 입력받고 각 장애물들을 석순과 종유석으로 분류합니다.

2. 석순과 종유석 각각을 높이에 대한 오름차순으로 정렬합니다.

3. 파괴해야 할 장애물의 최소 개수를 저장할 변수인 min을 생성하고 최소 개수에 해당하는 높이의 개수를 저장할 변수인 count를 생성합니다.

4. 높이가 1인 곳부터 해당 동굴의 높이까지 반복문을 돌면서 파괴해야 할 장애물의 최소 개수를 구하고 최소 개수에 해당하는 높이의 개수를 구합니다.

   1. 현재 높이에서 석순과 종유석 각각 이진 탐색을 통하여 파괴해야 할 장애물의 개수를 구한 후에 두 개수를 더하여 현재 높이에서 파괴해야 할 장애물의 총 개수를 구합니다.

      1) 최소 개수인 0을 start, 최대 개수인 (동굴 길이 / 2)를 end라는 변수에 설정합니다.
      2) start가 end보다 작은 값일 동안 반목문을 돌며 개수를 확인합니다.

      1. start와 end의 중간값을 mid라는 변수에 설정합니다.
      2. mid번째 장애물의 높이값이 현재 높이값보다 크거나 같다면 end의 값을 mid로 변경합니다.
      3. mid번째 장애물의 높이값이 현재 높이값보다 작다면 start의 값을 mid + 1로 변경합니다.

      3) 전체 장애물의 길이에서 end의 값을 뺀 값이 파괴해야 할 장애물의 개수가 되므로 해당 값을 반환합니다.

   2. 1번 과정에서 구한 파괴해야 할 장애물의 총 개수가 min값과 같다면, 즉 이전까지 구한 파괴해야 할 장애물의 개수의 최솟값과 같다면 최소 개수에 해당하는 높이의 개수를 1 증가시킵니다.

   3. 만약 min값이 1번 과정에서 구한 파괴해야 할 장애물의 총 개수보다 크다면 min값을 1번 과정에서 구한 파괴해야 할 장애물의 개수로 변경하고 최소 개수가 변경되었기 때문에 최소 개수에 해당하는 높이의 개수를 1로 초기화합니다.

5. 4번 과정을 통해 구한 파괴해야 할 장애물의 개수와 최소 개수에 해당하는 높이의 개수를 출력합니다.