3020_개똥벌레

Concept & Idea

우선 종유석과 석순을 구분하여 배열에 넣었다.
그리고 lower_bound와 upper_bound를 이용해서 장애물의 수를 count하고 배열에 높이의 수를 기록한다.
마지막에 최솟값을 출력하기 위해서, 원래 포문을 1부터 n까지 돌려야했는데 생각해보니 장애물이 0일수도 있기 때문에 이를 고침으로 맞을 수 있었다.

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,h;
int map[200001];
vector<int> up, down;
int obstacle[200001];
int main(){
    cin>>n>>h;
    for(int i=0; i<n; i++)
        cin>>map[i];
    for(int i=0; i<n; i++) {
        if(i%2==0)
            down.push_back(map[i]);
        else
            up.push_back(map[i]);
    }
    sort(up.begin(), up.end()); sort(down.begin(), down.end());
    for(int i=1; i<=h; i++) {
        int downIndex=lower_bound(down.begin(), down.end(), i)-down.begin();
        int temp = down.size()-downIndex;
        int upIndex = upper_bound(up.begin(), up.end(),h-i)-up.begin();
        temp+=up.size()-upIndex;
        obstacle[temp]++;
    }
    for(int i=0; i<=n; i++) {
        if(obstacle[i]!=0) {
            cout<<i<<" "<<obstacle[i]<<endl;
            break;
        }
    }
}

> 다른 테스트 케이스

input 14 5 1 3 4 2 2 4 3 4 3 3 3 2 3 3 output 7 2

Fealing

파라메트릭 서치인줄 알았는데,, 아니었다.
장애물의 최솟값을 Mid로 두고 서치를 하려고 했는데, 그 문제가 아니었다..
왜냐면 파라메트릭 서치처럼해서 탐색으로 장애물 갯수를 세려면, 거의 삼중 포문이 되어 시간초과가 나버려서 바로 다른 방법을 찾아 풀수있었다.