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

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

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

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

 

문제

 

입력

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 석순과 종유석을 구별해서 각 배열에 대입

2. 각 배열마다 오름차순 정렬

3. 각 높이의 구간별로 석순과 종유석 배열에서 upper_bound의 이진 탐색을 진행

4. 석순은 [석순 개수 - 높이 h에 대한 이진 탐색으로 찾은 index], 종유석은 [종유석 개수 - 높이 (H - h)이진 탐색으로 찾은 index]로 현재 높이의 구간에서 뚫어야 하는 장애물 개수 구하기

5. 뚫어야 하는 장애물 개수가 새로운 최솟값이면, 해당 값으로 변경 후, 구간 개수는 1개로 수정

6. 뚫어야 하는 장애물 개수가 기존 최솟값과 동일하면, 구간 개수를 1개 증가

 

과정

먼저, 석순과 종유석을 구별해서 각 배열에 대입합니다.

 

해당 문제에서 특정 높이의 구간에 있는 석순이나 종유석이 위치하면, 이를 파괴하면 됩니다.

즉, 석순이나 종유석의 순서는 상관이 없습니다.

석순이나 종유석의 순서를 오름차순으로 재배치하고, 현재 검사하고 있는 높이의 index만 구하면, index를 기준으로 앞 또는 뒤에 있는 모든 장애물을 파괴하므로, index로 파괴해야 하는 장애물 개수를 쉽게 구할 수 있습니다.

 

따라서, 먼저 석순과 종유석의 배열을 오름차순 정렬한 후, 현재 검사하고 있는 높이까지 있는 석순/종유석의 index를 구합니다.

 

만약에, 높이가 2~3의 구간에 개똥벌레가 있으면, 석순은 현재 검사하는 높이보다 낮은 경우에 파괴하지 않습니다.

즉, 높이가 2 이하인 석순의 개수를 제거합니다.

따라서, [현재 석순 배열의 개수 - 높이가 2일 때의 가장 마지막 index]로 파괴할 석순의 개수를 구할 수 있습니다.

가장 마지막 index를 구해야 하므로 이진 탐색에서 upper_bound로 구합니다.

 

종유석을 구하는 경우에는 전체 높이(H)에서 현재 검사하는 높이(h)를 빼서, 이진 탐색을 진행합니다.

 

 이러한 과정을 높이가 0~1부터, H-1 ~ H까지 반복합니다.

 

만약에, 뚫어야 하는 장애물 개수가 새로운 최솟값이면, 해당 값으로 변경한 후에 구간 개수를 1개로 변경합니다.

하지만, 뚫어야 하는 장애물 개수가 기존 최솟값과 동일하다면, 구간 개수를 1개 증가합니다.

 

이러한 과정을 거쳤을 때, 시간 복잡도는 500'000 {H 최대치} * 2 {석순/종유석 배열} * log(100'000 {석순/종유석 최대 개수})를 가집니다.

 

 

 

---

03. 정답 코드

// 골드 5 - 3020번 : 개똥벌레
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

// 석순과 종유석 구별
// 오름차순 후, 현재 높이보다 바로 한 칸 큰 것까지 찾아야 함. upper bound로 찾기

// N : 2~200'000
// H : 2~500'000

vector<int> g_up;
vector<int> g_down;

void inputData(const int N)
{
    g_up.reserve(N);
    g_down.reserve(N);

    int input;
    for(int i = 0; i < N; i++)
    {
        cin >> input;
        if(i % 2 == 0)
            g_down.push_back(input);
        else
            g_up.push_back(input);
    }

    // 오름차순 정렬
    sort(g_up.begin(), g_up.end());
    sort(g_down.begin(), g_down.end());
}

// upper_bound 찾기
int find(const vector<int>& vec, const int cur)
{
    int left = 0, right = vec.size();
    int mid;

    if(cur < vec[0]) return 0;
    if(cur > vec.back()) return right;

    while(left + 1 < right)
    {
        mid = (left + right) >> 1;

        if(vec[mid] <= cur)
            left = mid;
        else
            right = mid;
    }

    return right;
}

void simulate(const int N, const int H)
{
    int result = numeric_limits<int>::max();
    int count = 0;

    for(int cur = 0; cur < H; cur++)
    {
        int down = g_down.size() - find(g_down, cur);
        int up = g_up.size() - find(g_up, H - 1 - cur);

        int total = down + up;
        // 새로운 최솟값 발견
        if(result > total)
        {
            result = total;
            count = 1;
        }
        // 현재 최솟값과 동일
        else if(result == total)
            count++;
    }

    cout << result << " " << count << "\n";
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 장애물 개수 N, 높이 H
    int N, H;
    cin >> N >> H;

    inputData(N);
    simulate(N, H);
}

 

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!