[G5] 백준 1263번 시간 관리 C++ 우선순위 큐, 그리디 알고리즘

리뷰

 

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

골드 치고는 굉장히 쉬운 그리디 알고리즘 문제

 

 

전역 변수

• n : 작업의 개수를 저장할 변수
• Job : 작업을 정의할 구조체, 소요 시간 및 데드라인과 우선순위 큐용 cmp함수를 정의한다.

 

함수

없음

 

 

문제풀이

• n을 입력 받고, Job타입의 우선순위 큐 pq를 초기화 한다.
• n개의 작업의 소요 시작 및 데드라인을 입력 받고 pq에 push해준다.
• si가 최대 100만이니 정수형 변수 now를 100만보다 크게 설정해 준다.
• pq가 빌 때까지 즉, 모든 작업을 처리할 때 까지 루프를 수행한다.
• 만약 pq의 top보다 now가 크다면 pq의 top으로 now를 변경해 준다.
• 정수형 큐 q를 초기화 하고, now보다 크거나 같은 데드라인을 가진 작업을 pq에서 빼내 소요시간을 q로 push해준다.
• q에 있는 요소들을 탐색하며 소요 시간만큼 now의 값을 빼내준다.
• 모든 작업을 처리하고 나서 now가 0이상이라면 now를, 아니라면 -1을 출력해 주면 된다.

 

참고 사항

데드라인이 큰 순, 소요시간이 작은 순으로 정렬된 우선순위 큐를 사용하면 된다.

만약 모든 작업의 데드라인이 현재 시간보다 작다면 현재 시간을 가장 큰 데드라인으로 줄여주어야 한다.

 

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n;
struct Job {
	int t, s;
	bool operator<(const Job& other) const {
		if (s == other.s) return t > other.t;
		return s < other.s;
	}
};

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

	cin >> n;
	priority_queue<Job> pq;
	for (int i = 0; i < n; ++i) {
		int ti, si; cin >> ti >> si;
		pq.push({ ti, si });
	}
	
	int now = 1000001;
	while (!pq.empty()) {
		if (!pq.empty() && pq.top().s < now) now = pq.top().s;

		queue<int> q;
		while (!pq.empty() && pq.top().s >= now) {
			q.push(pq.top().t);
			pq.pop();
		}

		while (!q.empty()) {
			now -= q.front();
			q.pop();
		}
	}
	if (now >= 0) cout << now;
	else cout << -1;
}