[백준/C++] 21773 가희와 프로세스 1

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

코드

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

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);

typedef struct {
	int id;
	int time;
	int pr;
} pi;

struct cmp {
	bool operator() (pi a, pi b) {
		if (a.pr == b.pr) {
			return a.id > b.id;
		}
		else return a.pr < b.pr;
	}
};

int t, n;
priority_queue<pi, vector<pi>, cmp> pq;

int main() {
	FASTIO;
	cin >> t >> n;

	for (int i = 0, a, b, c; i < n; i++) {
		cin >> a >> b >> c;
		pq.push({ a,b,c });
	}

	for (int i = 0; i < t; i++) {
		pi now = pq.top();
		pq.pop();

		cout << now.id << "\n";
		now.pr--;
		now.time--;
		if (now.time > 0) pq.push(now);
	}
	return 0;
}

 

설명

프로세스를 정보를 저장해주는 구조체 생성 후 문제 조건대로 우선순위 큐를 만듭니다. 이후 반복문을 돌면서 현재의 pq.top 값을 가져와  프로세스를 실행하고 실행시간이 남아있다면 다시 우선순위 큐에 넣어줍니다.

 

느낀 점

보자마자 우선순위 큐를 이용하는 문제임을 파악했습니다. 그래서 프로세스를 원소로 갖는 pq를 만들고 문제대로 구현했습니다. 현재 수행 중인 프로세스를 제외한 프로세스의 우선순위가 증가하는 것은 곧 현재 수행 중인 프로세스의 우선순위가 줄어드는 것과 같습니다. 문제에서 프로세스의 우선순위를 비교 시에만 사용하므로 현재 프로세스의 정보만 변경해주면서 풀었고, 한 번에 통과했습니다!