백준 3020번: 개똥 벌레

문제링크 :https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

 문제설명 

 

1. 개똥벌레가 석순과 종유석으로 가득차있는 동굴에 갇혔다.

2. 개똥벌레가 최소로 석순과 종유석을 파괴하고 나갈수있는 최소 파괴 갯수와 그러한 구간을 출력하면된다.

 

 알고리즘 

 

1. 1번부터 i번 구간까지 그 구간으로 이동하였을때 파괴하는 종유석과 석순의 갯수를 lower_bound,upper_bound 를 이     용하여 구한다.

 

 코드 

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
 int INF = 987654321;
 
 
 
int main(void){
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int N, H;
 
    cin >> N >> H;
 
    vector<int> bottom(N / 2), top(N / 2);
 
    for (int i = 0; i < N / 2; i++) {
        cin >> bottom[i] >> top[i];
    }
 
 
    //오름 차순 정렬( lower_bound,upper_bound사용할려면 정렬되어있어야함)
    sort(bottom.begin(), bottom.end());
    sort(top.begin(), top.end());
 
    int result = INF;
    int cnt = 1;
    for (int i = 1; i <= H; i++) {
 
        //해당 높이에 겹치는 석순
        int brk = bottom.size() - (lower_bound(bottom.begin(), bottom.end(), i) - bottom.begin());
 
        //해당 높이에 겹치는 종유석
        brk += top.size() - (upper_bound(top.begin(), top.end(), H - i) - top.begin());
 
        if (result == brk)cnt++;
 
        //최소 파괴 수 갱신
        else if (result > brk) {
            result = brk;
            cnt = 1;
        }        
    }
    
    cout << result << " " << cnt << "\n";
}