[1700] 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

<문제>

운영체제에서 다루는 페이지 교체 알고리즘에서 발상을 얻을 수도 있다고한다.

플러그가 전부 찰때까지 꽂아주다, 다 찬 후부터는 현재 시점에서 필요한 시점이 가장 먼 플러그를 뽑아준다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, ans, a[101];
bool check[101];
vector<int> v;
int main(void) {
    cin >> n >> m;
    int i, j, k;
    for (i = 0; i < m; i++) cin >> a[i];
 
    for (i = 0; i < m; i++) {
        if (check[a[i]] == true) continue;
        if (v.size() < n) {
            v.push_back(a[i]);
            check[a[i]] = true;
            continue;
        }
        ans++;
        int cur = 0, curIdx = 0;
        for (j = 0; j < n; j++) {
            for (k = i + 1; k < m && a[k] != v[j]; k++)
                ;
            if (k == m) {
                curIdx = j;
                break;
            }
            int score = k - i;
            if (cur < score) {
                cur = score;
                curIdx = j;
            }
        }
        check[v[curIdx]] = false;
        v[curIdx] = a[i];
        check[a[i]] = true;
    }
    cout << ans;
    return 0;
}