[c++] 백준 #3020 개똥벌레 (190915)

< 풀이 >

종유석이든 석순이든 어느 위치에 있는 지는 중요하지 않기에 정렬을 한다. 이후, H개의 높이에서 다 잘라보는데 각 높이마다 부술 수 있는 것의 개수는 정렬된 배열에서 lower_bound를 이용해서 O(logN)에 구할 수 있다. 이를 이용하면 복잡도는 O(NlogN + HlogN)이 된다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, H; cin >> N >> H;
    vector<int> grow_up; // 석순
    vector<int> grow_down; // 종유석
    for(int i=1; i<=N;i++){
        int temp; cin >> temp;
        if (i % 2 > 0) { // 석순
            grow_up.pb(temp);
        } // 종유석
        else grow_down.pb(temp);
    }
    sort(grow_up.begin(), grow_up.end());
    sort(grow_down.begin(), grow_down.end());
    // 높이 L일 때 (H – L) + 1 이상의 길이를 가진 종유석들을 다 자름(H-L+1, H-L+2, ...)
    // L번째 구간으로 자르면 L 이상의 길이를 가진 석순을 다 자름(L, L+1, ...)
    // lower bound : key 값이 없으면 key값보다 큰 가장 작은 정수 값을 반환, 아니면 맨 처음 key 값이 나오는 위치 반환, 자기자신 포함되어야 하므로 lower bound 찾음
    vector<int> ans(N+1, 0);
    for(int L=1; L<=H; L++){
        int not_cut_up = lower_bound(grow_up.begin(), grow_up.end(), L) - grow_up.begin(); // Level 1 = 0.5에서 자르니까, 1, 2, ... 가 잘린다, 이 값 이하의 값 갯수를 찾는다
        int not_cut_down = lower_bound(grow_down.begin(), grow_down.end(), H-L+1) - grow_down.begin(); // Level 2 = 1.5에서 자르면 H-1이 잘린다, 이 값 이하의 값 갯수를 찾는다
        ans[N-(not_cut_up+not_cut_down)]++; // 전체 N개 중 안잘리는 갯수 뺀다
    }
    for(int i=0; i<=N;i++){
        if (ans[i]){
            cout << i << " " << ans[i] << '\n';
            return 0;
        }
    }
    return 0;
}