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

www.acmicpc.net/problem/14464

14464번: 소가 길을 건너간 이유 4

 

 

 

알고리즘 종류

우선순위 큐

정렬

 

 

 

사고 과정

1. 닭의 시간을 오름차순으로 정렬하여 저장합니다.

2. 소의 끝나는 시간을 기준으로 오름차순 정렬합니다. 저는 우선순위 큐를 이용해서 저장했습니다.

3. 소를 하나씩 꺼내서 Ai ~ Bi에 속하는 닭이 있는지 확인합니다. 닭을 확인했으면, 체크합니다.

 

 

 

구현(C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Cow{
    int s,e;
};
 
struct cmp{
    bool operator()(Cow a, Cow b){
        if(a.e != b.e) return a.e > b.e;
        return a.s > b.s;
    }
};
 
int c, n;
int t;
int ans=0;
 
vector<pair<int, int> > chicken; // 시간, 수행했는지 여부  
priority_queue<Cow, vector<Cow>, cmp> cow; // 끝나는 시간 기준으로 오름차순 저장. 최소 힙. 
 
 
bool c_cmp(pair<int, int> a, pair<int, int> b){
    return a.first < b.first;
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> c >> n;
 
    for(int i=0; i<c; i++){
        cin >> t;
        chicken.push_back({t, 0});
    }
    
    int s, e;
    for(int i=0; i<n; i++){
        cin >> s >> e;
        cow.push({s, e});
    }
    
    sort(chicken.begin(), chicken.end(), c_cmp);
    
    // 소를 하나씩 꺼내서 닭의 시간과 맞는지 확인하기  
    while(!cow.empty()){
        for(int i=0; i<c; i++){
            if(chicken[i].first >= cow.top().s && chicken[i].first <= cow.top().e && chicken[i].second == 0){
                ans ++;
                chicken[i].second = 1;
                break;
            }
        }
        cow.pop();
    }
 
    cout << ans << endl;
}

 

 

 

시행착오