백준 3020번 개똥벌레 - C++ 풀이

---

 

1. 종유석과 석순을 따로 저장한다.
2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다.
3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다.

 

1. 종유석과 석순을 따로 저장한다.

 두 장애물의 방향이 다르므로 종유석과 석순을 따로 저장한다. 

 

2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다.

 종유석은 끝부분이 h 미만인 것들을 파괴해야 하고, 석순은 끝부분이 h 초과인 것들을 파괴해야 한다. 따라서 종유석과 석순을 각각 정렬한 뒤, 이분 탐색을 이용하여 파괴해야 하는 개수를 각각 구해주면 된다.

 

3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다.

 총 H개의 구간에 대해 파괴해야 하는 장애물의 개수를 모두 구한 뒤 최솟값을 찾는다. 최종 시간 복잡도는 O(HlogN)이다.

반응형

---

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

using namespace std;

int N, H;
vector<int> up, down; // up=종유석, down=석순

pair<int, int> optimize() {
    pair<int, int> ret = {N, 1};
    
    sort(up.begin(), up.end());
    sort(down.begin(), down.end());
    
    for (int h=0; h<H; h++) {
        int down_cnt = down.size() - (upper_bound(down.begin(), down.end(), 0.5+h) - down.begin());
        int up_cnt = upper_bound(up.begin(), up.end(), 0.5+h) - up.begin();
        int total_cnt = up_cnt + down_cnt;
        
        if (total_cnt < ret.first) ret = {total_cnt, 1};
        else if (total_cnt == ret.first) ret.second++;
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> H;
    
    for (int i=0; i<N; i++) {
        int temp;
        cin >> temp;
        
        if (i % 2 == 0) down.push_back(temp);
        else up.push_back(H-temp);
    }
    
    auto ans = optimize();
    cout << ans.first << " " << ans.second;

    return 0;
}