이번에는 백준 14469번 소가 길을 건너간 이유 3 문제를 풀어보았습니다.
문제를 처음 봤을 때 소는 도착한 순서대로만 검문을 받을 수 있으므로, 먼저 도착 시간 기준으로 정렬하면 된다고 생각했습니다.
이후 현재 시간과 다음 소의 도착 시간을 비교하면서 검문이 끝나는 시간을 계속 갱신하는 방식으로 구현하였습니다.
문제 설명
각 소마다
- 도착 시간
- 검문 시간
이 주어집니다.
한 번에 한 마리만 검문을 받을 수 있을 때, 모든 소가 입장을 마치는 시간을 구하는 문제입니다.
풀이 아이디어
먼저 모든 소를 도착 시간 기준으로 오름차순 정렬하였습니다.
현재 시간이 다음 소의 도착 시간보다 크거나 같다면, 이미 기다리고 있는 상태이므로 현재 시간에 검문 시간을 더하였습니다.
반대로 아직 다음 소가 도착하지 않았다면, 해당 소가 도착한 시각부터 검문을 시작하므로 도착 시간과 검문 시간을 더한 값으로 현재 시간을 갱신하였습니다.
이 과정을 모든 소에 대해 반복하면 마지막 검문이 끝나는 시간을 구할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
struct cmp {
bool operator() (pair<int, int> a, pair<int, int> b){
if (a.first != b.first)
return a.first > b.first;
return a.second > b.second;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
for (int i=0; i<n; i++) {
int arrive, how;
cin >> arrive >> how;
pq.push({arrive, how});
}
int t = 1;
while(!pq.empty()) {
if (pq.top().first <= t) {
t += pq.top().second;
pq.pop();
}
else {
t = pq.top().first + pq.top().second;
pq.pop();
}
}
cout << t;
return 0;
}풀이 흐름
- 모든 소의 정보를 입력받습니다.
- 도착 시간 기준으로 오름차순 정렬합니다.
- 현재 시간과 다음 소의 도착 시간을 비교합니다.
- 이미 소가 도착해 있다면 현재 시간에 검문 시간을 더합니다.
- 아직 도착하지 않았다면 도착 시간부터 검문을 시작합니다.
- 마지막 검문이 끝난 시간을 출력합니다.
구현 포인트
1. 우선순위 큐 정렬
도착 시간이 빠른 소부터 처리하기 위해 우선순위 큐를 사용하였습니다.
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;비교 함수는 도착 시간이 작은 순서대로 나오도록 구현하였습니다.
struct cmp {
bool operator() (pair<int, int> a, pair<int, int> b){
if (a.first != b.first)
return a.first > b.first;
return a.second > b.second;
}
};priority_queue의 비교 함수는 sort()와 기준이 반대라는 점을 이용하였습니다.
2. 이미 도착한 소 처리
현재 시간이 소의 도착 시간보다 크거나 같다면 이미 줄을 서 있는 상태입니다.
if (pq.top().first <= t) {
t += pq.top().second;
}현재 검문이 끝난 직후 바로 다음 소의 검문을 시작하도록 구현하였습니다.
3. 아직 도착하지 않은 소 처리
다음 소가 아직 도착하지 않았다면 기다렸다가 검문을 시작해야 합니다.
t = pq.top().first + pq.top().second;도착 시간부터 검문을 시작하여 검문 시간을 더해 현재 시간을 갱신하였습니다.
4. 현재 시간 관리
t는 현재까지 모든 검문이 끝난 시각을 의미합니다.
각 소를 처리할 때마다
- 바로 검문할 수 있는 경우
- 기다려야 하는 경우
를 구분하여 t를 계속 갱신하였습니다.
모든 소를 처리한 뒤의 t가 모든 소의 입장이 끝나는 시간이 됩니다.
