190214 BOJ 3020번 개똥벌레

정렬, 이분 탐색

- 정렬하고 나서 높이가 500000개 이므로 높이 하나 씩 탐색하는 방식으로 풀었다.

- 다른 사람들의 코드를 보니 입력 받자마자 배열에 갯수를 추가하는 방식으로 풀 수도 있더라.

  N이 200000개 밖에 안되니 충분히 가능한 풀이고 내 풀이보다 더 빠르다.

풀이

1. 석순과 종유석을 각각 배열을 만들어 입력받는다

2. 두 배열을 정렬한다.

3. 아래 식에 따라 높이 1 부터 H 까지 수행한다.

높이 1 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 0 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 H - 1 이하 갯수)

높이 2 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 1 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 H - 2 이하 갯수)

...

높이 H 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 H - 1 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 0 이하 갯수)

여기서 배열은 정렬된 상태이므로 lower_bound를 이용해 높이가 x 이하인 갯수를 찾을 수 있다.

arr[8] = { 1,1,1,2,3,3,4,5 } 에서 lower_bound(arr, arr+8, 2) - arr 을 수행하면 

2가 들어갈 수 있는 인덱스 3을 얻을 수 있는데 이것은 즉 2 이하의 요소 갯수가 3 이라는 것을 알 수 있다.

4. 수행하면서 최소값과 구간 수를 갱신한다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define ll long long
#define mp(a,b) make_pair(a,b)
#define sws ios::sync_with_stdio(false), cin.tie()
#define MAX 1000000000
using namespace std;
int N, H, tmp, ans = MAX, rng;
vector<int> A, B;
int main() {
    sws;
    cin >> N >> H;
    FOR(i, 0, N) {
        cin >> tmp;
        if (i % 2 == 0) A.push_back(tmp);
        else B.push_back(tmp);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    int totA = A.size(), totB = B.size();
    FOR(i, 1, H+1) {
        int x = totA - (lower_bound(A.begin(), A.end(), i) - A.begin());
        int y = totB - (lower_bound(B.begin(), B.end(), H - i + 1) - B.begin());
        if (ans > x + y) {
            ans = x + y;
            rng = 1;
        }
        else if (ans == x + y) rng++;
    }
    cout << ans << ' ' << rng;
}