[Algorithm]Baekjoon 3020번 :: 개똥벌레

https://www.acmicpc.net/problem/3020

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int n, h, a, b;
 
vector<int> bottom;
vector<int> top;
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> h;
 
    for (int i = 0; i < n / 2; ++i)
    {
        cin >> a >> b;
 
        bottom.push_back(a);
        top.push_back(b);
    }
 
    sort(bottom.begin(), bottom.end());
    sort(top.begin(), top.end());
 
    int answer = 0x3f3f3f3f;
    int answerCount = 0;
 
    for (int i = 1; i <= h; ++i)
    {
        int bottomCount = lower_bound(bottom.begin(), bottom.end(), i) - bottom.begin();
        bottomCount = bottom.size() - bottomCount; // 높이가 i일 때 부술 수 있는 석순의 개수.
 
        int topCount = lower_bound(top.begin(), top.end(), h - i + 1) - top.begin();
        topCount = top.size() - topCount; // 높이가 i일 때 부술 수 있는 종유석의 개수.
 
        int totalCount = bottomCount + topCount;
        
        if (totalCount < answer)
        {
            answer = totalCount;
            answerCount = 1;
        }
        else if (totalCount == answer)
        {
            ++answerCount;
        }
    }
 
    cout << answer << ' ' << answerCount;
}
 
 

 

최소한의 횟수로 종유석,석순을 부수고 끝까지 도달해야하는 문제.

 

골드5치고는 어려웠다고 느꼈는데, 사실 정렬해도 상관없다는 사실을 빨리 알아챘으면 더 쉽게 풀이했을 것 같다.

정렬시킨다음 각 높이를 기준으로 특정높이마다 큰 것들의 개수를 구한다음, 동굴높이에서 구한 개수를 빼주면 해당높이에서의 부서지는 종유석이나 석순의 개수를 구할 수 있다.

 

이 때 특정높이마다 큰것들의 개수를구할 때 lower_bound를 사용한다. lower_bound를 사용하든, 뭐 직접 이분탐색코드로 구현하든 하면 된다. lower_bound를 굳이 안쓸이유는 없으니 lower_bound를 사용한다.

lower_bound를 사용하면 특정값보다 같거나 큰 첫번째 이터레이터를 반환하니, begin()을 빼주면 인덱스가 구해진다.

전체사이즈(동굴높이)에서 이 인덱스를 빼주면 그게 곧 특정값보다 큰것들의 개수가 된다.

 

ex) 석순이 1 3 3 3 4     이렇게 주어졌을 경우, 개똥벌레가 구간1에서 부술 수 있는 개수를 구하려한다고 가정하자.

 

lower_bound에 매개변수로 1을 넘기면 리턴이터레이터값 - begin()을 할 경우 0이 나올것이다. 

1보다 같거나 큰 첫번째 인덱스는 0번째인덱스니까.

 

최종값이 0번째 인덱스라는 것은 해당 컨테이너에 있는 모든 값이 1보다 크다는거니까 해당 컨테이너사이즈에서 0을 뺀값, 즉 컨테이너사이즈값 자체가 부술 수 있는 개수가 된다.

 

이렇게 종유석도 구하면 된다. 종유석은 위에서 아래로 내려오니까 h - i + 1로 반전시켜주면 된다.

lower_bound는 시간복잡도 logN 이고 한번의 반복마다 두번수행(종유석,석순) 하고 이 반복을 h번만큼 하니까 

 

최종 시간복잡도는 500,000 * 2 * log (n/2) 가 된다.