[Greedy] BOJ 1700 멀티탭 스케줄링

문제 링크 : www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

평소에 전공지식 공부를 병행한 사람이라면 무언가 번뜩할 것이다.

이 문제는 페이지 교체 알고리즘에 빗대어 설명할 수 있기 때문이다.

[OS/운영체제] 페이지 교체 (Page Replacement) - (2)

한정된 멀티탭이 곧 프레임의 수와 같고, 각 전자기기들은 페이지와 같다.

이런 페이지 교체 알고리즘 중 반드시 가장 적은 수의 페이지 결함을 보장하는 것은 OPT(Optimal) 알고리즘이다.

즉 참조 문자열이 제시되었을 때, OPT 알고리즘을 구현해 멀티탭을 뽑는 최소의 횟수를 구하는 것이다.

OPT 알고리즘은 멀티탭에서 어떠한 기기를 빼야 할 때, 그 이후의 모든 전자기기 사용 예정 중 가장 늦게 등장하는 전자기기를 빼도록 동작한다.

(단, 페이지 교체 알고리즘에서는 최초 빈 프레임에 페이지를 할당할 때도 페이지 결함을 카운트하지만, 이 문제에서는 카운트하지 않는다.)

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <string>
 
using namespace std;
typedef pair<int, int> p;
 
int n, k;
vector<int> order;
bool runs[101];
 
int greedy() {
    vector<int> running;
    int victim, answer = 0;
 
    for (int i = 0; i < order.size(); i++) {
        int elec = order[i];        //기기 번호
 
        //이미 사용 중인 기기인 경우, continue
        if (runs[elec]) continue;
 
        //빈 구가 있다면 그 구를 사용
        if (running.size() < n) {
            running.push_back(elec);
            runs[elec] = true;
            continue;
        }
        //구가 꽉 찼다면, 앞으로 가장 늦게 사용할 기기를 뺀다.
        int t = 0;
        //뺄 기기 선택
        victim = 999;
        for (int j = 0; j < running.size(); j++) {
            int future = 999;
            for (int k = i + 1; k < order.size(); k++) {
                if (order[k] == running[j]) {
                    future = k;
                    break;
                }
            }
            if (future > t) {
                t = future;
                victim = j;
            }
        }
        //교체
        int target_number = running[victim];
        runs[target_number] = false;
        running[victim] = elec;
        runs[elec] = true;
 
        answer++;
    }
    return answer;
}
 
void init() {
    int elec;
    cin >> n >> k;
 
    for (int i = 0; i < k; i++) {
        cin >> elec;
        order.push_back(elec);
    }
 
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
 
    int answer = greedy();
    printf("%d\n", answer);
 
    return 0;
}