[C++] 백준 1700번 멀티탭 스케줄링

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

풀이

문제를 읽으면서 문제의 상황이 운영체제의 페이지 교체와 유사하다고 생각했다. 멀티탭은 페이지 프레임, 전기용품은 페이지라고 생각하면, 결국 최소 페이지 교체 횟수를 구해야 한다.
페이지 교체 기법 중 Optimal Algorithm은 가장 먼 미래에 참조되는 페이지를 교체하는 기법으로, 최소 교체 회수를 보장한다.
이 기법과 유사하게 전기용품 중 가장 나중에 사용하는 것을 멀티탭에서 제거하여 답을 구했다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N, K;
    int sequence[100];  // 전기용품 사용 순서
    int tab[101] = {0}; // 멀티탭에 꽂힌 전기용품 (0은 빈자리)

    cin >> N >> K;
    for(int i=0; i<K; i++) {
        cin >> sequence[i];
    }

    int ans = 0;
    
    for(int i=0; i<K; i++) {
        int cur = sequence[i];  // 현재 사용하려는 전기용품
        bool used = false;
        int j = 0;

        // 플러그를 빼지 않음
        for(j=0; j<N; j++) {
            if(tab[j] == cur) {  // 이미 꽂혀 있음
                used = true;
                break;
            } 
            if(!tab[j]) {  // 새로 꽂아야 하고, 꽂을 자리 있음
                tab[j] = cur; 
                used = true;
                break;
            }
        }
        if(used) continue;

        // 당분간 사용하지 않을 플러그 하나 빼고 cur 꽂기
        int last = 0;  // 가장 나중에 사용할 전기용품의 사용 순서
        int removed = -1;  // 가장 나중에 사용할(플러그 제거할) 전기용품
        for(j=0; j<N; j++) {  // 멀티탭에 꽂혀있는 전기용품들이 다시 사용될 시점 확인
            int x = i + 1;
            for(; x < K; x++) {
                if(tab[j] == sequence[x]) break;
            }

            if(last < x) {
                last = x;
                removed = j;
            }
        }
        tab[removed] = cur;
        ans++;
    }

    cout << ans;
    
    return 0;
}