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

www.acmicpc.net/problem/3020

3020번: 개똥벌레

이분 탐색 문제였습니다.

 

풀이방법

 1. 석순이나 종유석의 서순은 중요하지 않습니다. 높이에 따라 부서질지 아닐지만 확인하면 되기 때문에 정렬해도 문제였습니다. 석순과 종유석에 대한 입력을 두개의 vector 변수에 나눠 담고 오름차순으로 sort해줍니다.

 

 2. 구역을 1부터 시작해 height까지 loop를 돌며 최소의 장애물 파괴 수를 구합니다. 석순의 경우 선택한 구역(i) 이상의 높이를 가진 인덱스를 구해줍니다. 이러면 전체 길이에서 해당 인덱스를 빼준 값이 부셔야할 석순의 개수가 됩니다. 종유석의 경우는 거꾸로 매달려 있으므로 height - i를 초과하는 높이의 종유석만 파괴됩니다. 50만 높이에 대해 최대길이 10만의 석순과 종유석을 확인하기 때문에 O(50만log10만)의 시간복잡도를 갖습니다.

 3. 최솟값을 구했으면 같은 방식으로 해당 최솟값이 몇 번나오는지 세줍니다.

 

 4. 정답을 출력합니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, height, cnt, ans=0x3f3f3f3f;
vector <int> stalactite,stalagmite; //종유석, 석순
int main(){
    cin >> n >> height;
    for(int i = 0; i < n; i++) {
        int x; 
        cin >> x;
        if(i%2==0) stalagmite.push_back(x);
        else stalactite.push_back(x);
    }

    sort(stalagmite.begin(),stalagmite.end());
    sort(stalactite.begin(),stalactite.end());

    for(int i = 1; i <= height; i++){
        int idx = stalagmite.size() - (lower_bound(stalagmite.begin(),stalagmite.end(),i) - stalagmite.begin());
        int idx2 = stalactite.size() - (upper_bound(stalactite.begin(),stalactite.end(),height-i) - stalactite.begin());
        ans = min(ans,idx + idx2);
    }
    for(int i = 1; i <= height; i++){
        int idx = stalagmite.size() - (lower_bound(stalagmite.begin(),stalagmite.end(),i) - stalagmite.begin());
        int idx2 = stalactite.size() - (upper_bound(stalactite.begin(),stalactite.end(),height-i) - stalactite.begin());
        if(idx+idx2 == ans) cnt++;
    }

    cout << ans << ' ' << cnt << '\n';
}