2022.08.31 PS 일지

멀티탭 스케줄링

문제 링크

그리디 연습 겸 풀어봤다.

풀이

전기용품을 사용하려 할 때 다음의 두 가지 선택이 있다:

1. 이미 플러그가 꽂혀 있어서 그대로 사용한다
2. 기존의 플러그 중 하나를 뽑고 새 플러그를 꽂아 사용한다.

2번에서 어떤 플러그를 뽑을지 선택하는 것이 관건이다.

나중에 제일 적게 등장할 플러그를 뽑을 것인가? 아니다.

가장 나중에 등장할 플러그를 뽑을 것인가? 맞는 것 같다.

 

이는 가장 나중에 등장하지 않는 플러그를 뽑았다고 가정했을 때, 이 보다 가장 나중에 등장하는 플러그를 뽑는 것이 항상 유리하거나 같다는 발상을 통해 확인할 수 있다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 103, K = N;
int n, k;
int e[K], cnt;
int pre[K], nxt[K];
vector<ii> v;
bool ch[K];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    fill(nxt+1,nxt+k+1,1e8);
    rep(i,1,k) {
        cin >> e[i];
        nxt[pre[e[i]]] = i;
        pre[e[i]] = i;
    }
    rep(i,1,k) {
        if (ch[e[i]]) {
            v.erase(find_if(all(v),[&](ii x){ return x.second == e[i]; }));
            v.push_back({nxt[i],e[i]});
            continue;
        }
        ch[e[i]] = true;
        if (siz(v) == n) {
            cnt++;
            ch[(max_element(all(v)))->second] = false;
            v.erase(max_element(all(v)));
        }
        v.push_back({nxt[i],e[i]});
    }
    cout << cnt;
}

디버깅

WA×1: 이미 꽂혀있는 플러그라도 다음에 등장하는 위치를 갱신시켜 주는 작업이 필요한데, 이를 간과했다.

WA×2: 이전 pair쌍을 찾아 지우고 새로 삽입하여 갱신하려고 했다. 하지만 pair의 우선순위상 찾는 것이 불가능하기에 틀렸다.