[백준] 14464번 소가 길을 건너간 이유 4

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

 

 

문제 이해

이 문제는 C개의 닭과 N개의 소가 주어진다. 이때 각 닭들은 c초에 길을 건널 수 있으며 각 소들은 a, b가 주어지며 a부터 b까지 길을 건널 수 있다. 이때 닭은 소가 길을 건너줄 수 있는걸 도와줄 수 있으며 a <= c <= b일때 가능하다. 이때 최대로 소를 도와줄 수 있는 닭의 개수를 출력해야 한다.

 

문제 접근

 

처음엔 이분탐색을 사용하여 소의 시간을 끝시간에서 부터 시작 시간까지 탐색하려고 했지만 주어지는 시간이 10억이기에 불가능하다고 생각했다 따라서 오름차순으로 정렬하여 시간이 매칭될때 하나씩 더해주는 방법을 생각하였다. 하지만 반례를 생각해보면 무조건 시간이 매칭된다고 하나씩 더해주면 안된다

 

닭 : 5, 100

소 : (1, 100), (4, 6)

인 경우 5인 닭이 (1, 100)이 매칭이 된다 하지만 최적은 5인 닭이 (4, 6)과 매칭되고 100인 닭이 (1, 100)과 매칭되어야 하기 때문에 끝시간을 기준으로 가장 근접한 시간을 매칭해야 하기 때문에 우선순위 큐를 사용하였고

시작 시간을 기준으로 가능한 소들의 끝시간을 우선순위 큐에 넣어주었고 이후 닭의 시간과 우선순위 큐의 가장 작은 루트의 시간과 비교하여 가능하지 않은 경우 가능할때까지 pop을 해주었다.

 

이후 가능한 경우 하나를 pop해주고 개수를 1을 더해주었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

struct Tree {
    int Node, left, right;
};

const int INF = 1e9;
const int MAX = 200001;
const int MOD = 1e9 + 7;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int C, N;
priority_queue<int, vector<int>, greater<int>> pq;
vector<pii> v;
vector<int> arr;

void solve() {
    sort(v.begin(), v.end());
    sort(arr.begin(), arr.end());

    int idx = 0;
    int cnt = 0;

    for(int i = 0; i < C; i++) {

        int chicken = arr[i];

        while(idx != N && v[idx].first <= chicken) {        // 가능한 소들 탐색
            pq.push(v[idx].second);
            idx++;
        }

        while(!pq.empty() && pq.top() < chicken) {
            pq.pop();
        }

        if(!pq.empty()) {
            cnt++;
            pq.pop();
        }
    }

    cout << cnt;
}

void input() {
    cin >> C >> N;

    for(int i = 1; i <= C; i++) {
        int a;
        cin >> a;
        arr.push_back(a);
    }

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}