[백준][그리디] 1700 멀티탭 스케줄링 c++구현

목차

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

문제

 

문제 구현 방향

최적해를 나는 다음과 같이 짰다.

 

1. 앞으로 사용할 플러그인지 확인한다.
2. 앞으로 사용할 플러그가 아니라면 교체한다.
3. 모든 플러그가 앞으로 사용할 플러그라면 그 이후로 가장 늦게오는 플러그를 교체한다.

 

알고리즘 설명

Optimal Page Replacement라는 알고리즘으로 물리적 메모리에 있는 페이지 중 가장 미래에 참조되는 페이지를 쫓아내는 방법

 

그 외에도 FIFO(먼저 온 것부터 swap), LRU(가장 오래전에 참조, 많이 사용되지 않은 것부터 SWAP), LFU(참조 횟수가 가장 적었던 페이지를 교체), CLOCK(오랫동안 참조되지 않는 페이지 중 하나르르 SWAP)이 있다.

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<math.h>

using namespace std;

int N, K;

map<int, int>m;

vector<int> v;

vector<int> plug;

int rest[101] = { 0 };

int cnt = 0;


//그 번호의 콘센트를 반환하는 함수
int find(int num) {
    for (int i = 0; i < plug.size(); i++) {
        if (num == plug[i])
            return i;
    }
    return -1;
}

//이제 안써도 되는 콘센트 반환 함수
int find2() {
    for (int i = 0; i < plug.size(); i++) {
        if (0 == m[plug[i]])
            return i;
    }
    return -1;
}


//떨어진 거리별로 순위를 매겨 가장 멀리 떨어진 것을 반환하는 함수
int find3(int num) {
    fill(rest, rest + 100, 0);
    for (int j = 0; j < plug.size(); j++) {
        int start = num;
        int res = 0;
        while (true) {
            if (start >= v.size() - 1)
                break;
            if (plug[j] == v[start])
                break;
            res++;
            start++;
        }
        rest[plug[j]] = res;
    }
    int m = 0;
    int idx = 0;
    for (int i = 0; i < 100; i++) {
        if (m < rest[i]) {
            m = rest[i];
            idx = i;
        }
    }
    return find(idx);
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int num;
    cin >> N >> K;

    for (int i = 0; i < K; i++) {
        cin >> num;
        //플러그 번호와 개수별로 저장
        if (m[num])
            m[num]++;
        else
            m[num] = 1;
        //미리 플러그 순서 저장
        v.push_back(num);
    }

    for (int i = 0; i < v.size(); i++) {
        //사용했으니 감소
        m[v[i]]--;
        //플러그에 꽂힌 개수가 여유 있을 경우
        if (plug.size() < N) {
            int idx = find(v[i]); //이미 그 번호의 플러그가 꽂혀있는 경우 아무것도 안해도됨
            if (idx ==-1) {
                plug.push_back(v[i]);
            }
        }
        //없을 경우
        else {
            int idx = find(v[i]); //이미 그 번호의 플러그가 꽂혀있는 경우 아무것도 안해도됨

            if (idx == -1) {  //아닐 경우 교체해야 함
                int idx2 = find2();
                // 사용이 멀은 플러그를 교체
                if (idx2 == -1) {
                    int idx3 = find3(i);
                    plug[idx3] = v[i];   
            }
                else {
                    plug[idx2] = v[i];
                }
                cnt++;
            }
           
        }
    }
    cout << cnt;
}