[백준] 3020번 개똥벌레 (C++)

문제 링크

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

3020번: 개똥벌레

 

문제 설명

아래에서부터 자라는 석순과 위에서부터 자라는 종유석의 높이가 주어진다.

개똥벌레는 높이에 따라 나누어진 구간을 지나가게 되는데, 이때 석순이나 종유석이 존재하면

해당 장애물을 부수고 지나간다.

이 때 개똥벌레가 파괴해야 하는 장애물의 최솟값과, 그러한 구간의 총개수를 구해야 한다.

 

사고 과정

이전까지 풀어왔던 이진탐색 문제들처럼 left와 right 변수를 설정하여 해결하려 하였다.

석순과 종유석을 따로 입력 받고 오름차순으로 정렬한 뒤,

부셔야 하는 장애물이 최솟값이 되는 구간의 높이를 높이의 값을 변경해가며 이진탐색으로 찾고자 하였다.

하지만 입력 받은 숫자들을 정렬하든 정렬하지 않든 구간에 따라 부셔야 하는 장애물의 개수는 변하지 않았고,

장애물의 개수에 따라 높이의 값을 변경하고자 하였지만,

높이가 작아진다고 해서, 혹은 높아진다고 해서 장애물의 개수가 확정적으로 줄거나 늘어나는 것이 아니었다.

 

결국 높이로 구분된 모든 구간에 대해서 몇 개의 장애물이 존재하는지 확인해야 한다는 생각이 들었다.

해당 문제에서는 최대 O(NlogN) 알고리즘이 요구되고 모든 구간에 대해 장애물을 구하는 것은

필연적으로 O(N)에 해당했기 때문에, 선택된 구간의 장애물을 구하는 과정에서는 O(logN)의 시간 복잡도를 가져야 했다.

 

해결 방법

따라서 선택된 구간의 장애물을 구하는 과정은 이분탐색을 활용했다.

목표는 각각 정렬된 석순과 종유석 배열과  구간의 높이가 주어졌을 때, 개똥벌레가 부술 장애물의 수를 구하는 것이다.

 

먼저 아래에서 자라는 석순을 생각해보면, 오름 차순으로 정렬되어있기 때문에

주어진 높이 h 이상인 값이 처음 등장하는 인덱스를 구하면 장애물의 개수를 구할 수 있을 것이다.

즉, 석순에서의 장애물의 경우, 장애물의 개수 = (총 석순의 개수) - (h 이상의 값을 처음 가진 인덱스)가 된다.

 

위에서 자라는 종유석은 석순과 약간 다르다.

백준에서 주어진 예시를 보며 생각해보자.

주어진 높이 h가 4인 경우 개똥벌레가 부수게 될 장애물의 개수를 구한다고 해보자.

석순의 경우에는 높이가 4이상의 값을 처음 가지고 있는 인덱스를 찾아, 총석순의 개수에서 빼주면 되었다.

하지만 위에서 볼 수 있듯, 종유석의 경우에는 4이상이 아닌 2 이상인 값을 가진 인덱스를 찾아야 한다.

여기서 2는 최대 높이 H에 주어진 높이 h를 빼고 1을 더한 값이다.

즉, 종유석에서의 장애물의 개수 = (총 종유석의 개수) - (H - h + 1 이상의 값을 처음 가진 인덱스)가 된다.

 

여기서 중요한 점은 인덱스를 찾는 과정은 이분 탐색을 활용해야 한다는 것이다.

석순과 종유석 각각은 N/2개의 원소를 가지고 있으므로, 

left = 0, right = N/2 -1의 값을 초기값으로 시작하여 left와 right의 중간값인 mid가 가리키는 원소 값에 따라

left와 right를 움직여가며 '조건을 만족하는 값을 처음 가진 인덱스'를 찾아야 한다.

필자는 직접 함수를 설정하여 이분 탐색을 구현했지만,

C++의 lower_bound를 활용하는 것도 하나의 방법일 것 같다.

(lower_bound 설명과 직접 구현하는 방법, https://blog.joonas.io/153)

 

위의 방법을 토대로 주어진 구간에서 석순과 종유석에서의 장애물의 개수를 구하면

이전에 구해진 최소 장애물의 개수와 비교하여 최종 출력에 활용될 값들을 갱신해나간다.

만약 최소 장애물의 개수가 갱신되었다면,

즉, 현재 계산된 장애물의 개수가 이전까지 최소로서 여겨졌던 장애물의 개수보다 적다면

최소 장애물을 가진 구간의 개수 (코드의 cnt 변수)를 1로 초기화해주고 최솟값 (코드의 Min 변수) 또한 초기화해준다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, H;
int bot[100001];
int top[100001];

void init();
void input();
int crash_bot(int num);
int crash_top(int num);
void solve();

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

void input()
{
    cin >> N >> H;

    for (int i = 0; i < N / 2; i++)
    {
        cin >> bot[i];
        cin >> top[i];
    }
}

int crash_bot(int num)
{
    int left = 0;
    int right = (N / 2) - 1;
    int mid;

    while (left <= right)
    {
        mid = (left + right) / 2;

        if (bot[mid] < num)
            left = mid + 1;

        else
            right = mid - 1;
    }
    return N / 2 - left;
}

int crash_top(int num)
{
    int left = 0;
    int right = N / 2 - 1;
    int mid;

    while (left <= right)
    {
        mid = (left + right) / 2;

        if (top[mid] < num)
            left = mid + 1;

        else
            right = mid - 1;
    }

    return N / 2 - left;
}

void solve()
{
    sort(bot, bot + N / 2);
    sort(top, top + N / 2);

    int cnt = 0;
    int Min = N + 1;

    for (int h = 1; h <= H; h++)
    {
        int num = crash_bot(h) + crash_top(H - h + 1);

        if (num < Min)
        {
            cnt = 1;
            Min = num;
        }
        else if (num == Min)
        {
            cnt++;
        }
    }
    cout << Min << " " << cnt;
}

int main()
{
    init();
    input();
    solve();
    return 0;
}