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

문제링크 : https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, H, arr1[200001], arr2[200001];
int result = MAX, result_cnt;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> H;
    for(int i=0; i<N/2; i++) cin >> arr1[i] >> arr2[i]; //석순, 종유석

    sort(arr1, arr1+N/2);
    sort(arr2, arr2+N/2);

    for(int i=1; i<=H; i++)
    {
        int pos1 = lower_bound(arr1, arr1+N/2, i) - arr1; //i번째 석순 처음 나오는 위치
        int pos2 = upper_bound(arr2, arr2+N/2, H-i) - arr2; //i번째 석순과 겹치는 종유석이 처음 나오는 위치
        int cnt = N - (pos1 + pos2); //현재 i 기준 부수는 갯수

        if(result == cnt) result_cnt++; //구간 갯수 증가
        if(result > cnt)
        {
            result = cnt; //최솟값 갱신
            result_cnt = 1; //구간 체크 시작
        }
    }

    cout << result << " " << result_cnt; //최솟값과 해당 최솟값 구간 갯수

    return 0;
}

 

석순과 종유석이 번갈아 나오므로, 이에 맞게 입력을 받아줘야 한다.

이후 현재 석순의 위치를 기준으로 더 큰 값이 몇개 있는지, 해당 석순과 겹치는 종유석이 몇 개 있는지를 이분탐색을 통해 탐색하게 된다.

이분 탐색을 위해 각 입력받은 배열을 모두 정렬해주고 시작한다.

 

먼저 lower_bound를 통해 현재 i번째 석순이 처음 나오는 위치를 찾는다.

정렬이 되어있기 때문에 이후에 나오는 석순들은 모두 같이 부셔지게 된다.

 

다음으로 Upper_bound를 통해 현재 i번째 석순과 겹치게되는 종유석의 위치를 찾는다.

겹치게 되는 위치는 H-i를 한 값보다 큰 값이 나오는 위치이다.

그냥 H-i를 한 위치는 겹치지 않고 딱 맞는 위치이기 때문에 부셔지지 않아서 Upper_bound를 통해 해당 위치보다 큰 위치를 찾게 된다.

 

이제 총 길이인 N에서 구했던 위치들의 합을 빼주면 된다.

lower_bound의 결과가 0이라면, 뒤에 있는 석순들은 모두 부셔진다.

따라서 N/2 - pos1을 하면 부셔지는 석순의 갯수들을 알 수 있다.

 

마찬가지로 Upper_bound의 결과가 3이라면, 4이상의 종유석들은 모두 부셔진다.

따라서 N/2 - pos2를 하면 부셔지는 종유석의 갯수들을 알 수 있다.

 

이를 합하면 N/2 - pos1 + N/2 - pos2이므로, 결국 N - (pos1 + pos2) 이다.

이렇게 구한 현재 i 기준 부수는 총 장애물의 갯수를 토대로 다음 구간도 갯수가 같다면 구간을 증가시키고,

다음 구간이 갯수가 더 적다면 최소값 갱신민 구간 갯수 또한 다시 1부터 시작하게 된다.