[BOJ] 백준 3020 개똥벌레

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

Approach

- 모든 지점(높이)에 대해서 N개의 장애물(종순, 석순)과 부딪히는지 확인한다면 TLE

- 정렬 + 이분탐색을 통해 구할 수 있다.

▶ 합병 정렬(Merge Sort) 

▶ Binary Search (이분 탐색) 

▶ Parametric Search  

 

① 이분 탐색 (lower_bound와 upper_bound) 하기 위해서 원소를 정렬 합니다.

top = {2, 2, 3, 3, 3, 4, 4}

bottom = {1, 2, 3, 3, 3, 3, 4}

 

② 정렬된 원소에서 특정 높이에서 개똥벌레가 출발할 때, 부딪히는 장애물 개수를 구해야한다.

출발 높이 pivot = 4라고 했을 때, bottom = {1, 2, 3, 3, 3, 3, 4} 에서

6개 피할 수 있고, 1개 충돌한다.

즉, 높이 4 이상인 석순(bottom)을 찾아내는데, bottom[6] = 4 로 탐색된다.

 

마찬가지로 top = {2, 2, 3, 3, 3, 4, 4} 에서는 

{Height - pivot} = 5 - 4 = 1 이하인 곳을 찾는데 (upper_bound로 탐색)

존재하지 않으므로 0 개이다. 피할 수 있는 장애물이 없다는 것을 의미.

 

③ 전체 장애물 개수 (N)에서 피할 수 있는 장애물 개수 제외

14 - 6 = 8 을 도출할 수 있다.

이렇게 pivot을 1 ~ H 까지 설정해서 최솟값과 개수를 구할 수 있다.

(최소값이 갱신될 때, 찾은 개수도 1로 갱신해준다.)

 

<개똥벌레 출발 높이 = 5 인 경우>

bottom = {1, 2, 3, 3, 3, 3, 4} 이며, top = {2, 2, 3, 3, 3, 4, 4}

- 석순(bottom) 피할 수 있는 개수 → 7개

- 종순(top) 필할 수 있는 개수 → 0 개

- 장애물 N개와 부딪힌 개수 N - 7 - 0 = 7

---

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 2e5 + 2;
int bottom[MAX_N / 2], top[MAX_N / 2];
int ansMinVal = MAX_N, ansCnt;
int N, H, tmp;

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &H);

    // 석순(bottom)과 종순(top) 입력 받기
    for (int i = 0; i < N / 2; i++)
    {
        scanf("%d %d", &bottom[i], &top[i]);
    }

    sort(bottom, bottom + (N / 2)); // 석순(bottom) 정렬
    sort(top, top + (N / 2)); // 정순(top) 정렬

    // 각 높이 기준으로 부딪히는 장애물 개수 확인
    for (int pivot = 1; pivot <= H; pivot++)
    {
        tmp = lower_bound(bottom, bottom + (N / 2), pivot) - bottom;
        tmp += upper_bound(top, top + (N / 2), H - pivot) - top;
        tmp = N - tmp;
        // 현재 기준이 되는 최솟값과 동일한 경우
        if (ansMinVal == tmp)
        {
            ansCnt++;
        }
        // 보다 적게 장애물을 부딪히는 경우
        else if (ansMinVal > tmp)
        {
            ansMinVal = tmp;
            ansCnt = 1;
        }
    }
    printf("%d %d\n", ansMinVal, ansCnt);
}

 

함수 직접 구현 Ver.

정렬을 Merge Sort로 직접 구현하고,

lower_bound와 upper_bound 도 직접 구현하였다.

[C++] lower_bound, upper_bound 사용해보기 

[C++] lower_bound, upper_bound 사용해보기

 

앞서 설명한 로직과는 조금 차이가 있으나, 접근 방식 자체는 크게 다르지 않다.

- 각 기준(pivot) 층에서 장애물 크기가 가장 작은 것을 이분탐색해서 해당 층의 장애물 개수 확인

- 장애물 개수 중 최소값과 해당 최소값을 가지는 층 개수 출력

#include <stdio.h>

inline int _min(int A, int B) { return A < B ? A : B; }
const int MAX_N = 2e5 + 2;
const int MAX_HEIGHT = 5e5 + 2;
int bottom[MAX_N / 2], top[MAX_N / 2], obstacles[MAX_HEIGHT];
int ansMinVal;
int N, H, tmp, trr[MAX_N / 2];

void mergeSort(int *arr, int start, int end) 
{
	// 0. base condition
	if (start >= end) return;

	// 1. divide
	int mid = (start + end) / 2;

	// 2. conquer
	mergeSort(arr, start, mid);
	mergeSort(arr, mid + 1, end);

	// 3. merge
	int i = start, j = mid + 1, k = start;
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j])
			trr[k++] = arr[i++];
		else
			trr[k++] = arr[j++];
	}
	while (i <= mid) trr[k++] = arr[i++];
	while (j <= end) trr[k++] = arr[j++];

	// 4. copy
	for (i = start; i <= end; ++i) {
		arr[i] = trr[i];
	}
}

void init()
{
	for (int i = 0; i <= H; i++)
	{
		obstacles[i] = 0;
	}
	ansMinVal = MAX_N;
}

int main() {
	// freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &H);
	init();
	// 석순(bottom)과 종순(top) 입력 받기
	for (int i = 0; i < N / 2; i++)
	{
		scanf("%d %d", &bottom[i], &top[i]);
	}

	mergeSort(bottom, 0, (N / 2) - 1); // 석순(bottom) 정렬
	mergeSort(top, 0, (N / 2) - 1); // 정순(top) 정렬

	// 각 높이 기준으로 부딪히는 장애물 개수 확인
	for (int i = 1; i <= H; i++)
	{
		int l = 0;
		int r = N / 2 - 1;
		int bottomCnt = 0;
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (bottom[mid] >= i)
			{
				bottomCnt = (N / 2) - mid;
				r = mid - 1;
			}
			else
				l = mid + 1;
		}

		int topCnt = 0;
		l = 0;
		r = N / 2 - 1;
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (H - top[mid] < i)
			{
				topCnt = (N / 2) - mid;
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
		ansMinVal = _min(ansMinVal, topCnt + bottomCnt);
		obstacles[topCnt + bottomCnt]++;
	}
	printf("%d %d\n", ansMinVal, obstacles[ansMinVal]);
}