BOJ 20772 : Scheduler

• 문제 링크 : boj.kr/20772
• 난이도 : G4
• 태그 : 우선순위 큐

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

struct compare {
    bool operator()(pii &a, pii &b) {
        if(a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    }
};

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

    int n, t;
    cin >> n >> t;
    
    priority_queue<pii, vector<pii>, compare> _pq;
    vector<int> prio(n);
    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        cin >> prio[i];
        _pq.push({prio[i], i});
    }

    for(int i = 1; i <= t; i++) {
        int id = _pq.top().second; _pq.pop();
        ans[id]++;
        _pq.push({prio[id]-i, id});
    }

    for(auto u : ans) {
        cout << u << " ";
    }

    return 0;
}

---

풀이

현재 시각을 T, 해당 프로세스의 마지막 실행 시간을 L_i라고 할때, t_i를 T-L_i라고 할 수 있다. 

따라서 각 프로세스의 우선순위는 p_i + T - L_i라고 할 수 있고, 여기서 T는 모든 프로세스에 동일하게 적용되는 상수이므로 p_i - L_i라고 할 수 있다.

각 프로세스의 우선순위를 p_i - L_i라고 하면, 매 시간마다 우선순위를 갱신하지 않아도 되므로 우선순위 큐를 이용할 수 있다. 문제에서 요구한대로 comparator를 구현하면 해결할 수 있다.