boj 14464 소가 길을 건너간 이유 4

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

 

소는 A ~ B 시간 사이에만 이동할 수 있고, 닭은 T 시간에만 도움을 줄 수 있습니다.

즉 A <= T <= B 가 되어야 닭이 소를 도와줄 수 있습니다.

 

구현은 간단합니다.

가장 빠르게 도움을 줄 수 있는 닭을 찾기 위해 닭은 오름차순으로 정렬합니다.

그리고 소는 끝시간 기준 오름차순으로 정렬합니다.

이후에는 소 한마리씩 순회하여 도움을 받을 적절한 닭을 찾아주시면 됩니다.

 

범위가 각각 2만이기 때문에 TLE가 나오지 않을까 생각했지만 N * M으로도 풀리는 문제였습니다.

아마 중간에 적절한 답을 찾으면 break를 해주면서 시간이 어느정도 단축되는 것으로 보입니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 20001
using namespace std;
typedef pair<int, int> pii;
 
int list[MAX];
pii cow[MAX];
int N, M;
 
void func() {
    sort(list, list + N);
    sort(cow, cow + M, [](pii a, pii b) {
        return a.second < b.second;
    });
 
    int ret = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (list[j] == -1) continue;
            if (cow[i].first > list[j] || list[j] > cow[i].second) continue;
 
            ret++;
            list[j] = -1;
            break;
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
 
    for (int i = 0; i < M; i++) {
        cin >> cow[i].first >> cow[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}