백준 1700번 멀티탭 스케줄링 - C++(cpp) 풀이

---

 

1. 이미 꽂혀있다면 스킵한다.
2. 빈 자리가 있다면 빈 자리에 꽂는다.
3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다.

 

1. 이미 꽂혀있다면 스킵한다.

 이미 꽂혀있다면 스킵해도 된다.

 

2. 빈 자리가 있다면 빈 자리에 꽂는다.

 빈 자리가 있다면 빈 자리를 채우면 된다.

 

3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다.

 문제는 빈 자리가 없는 경우인데, 이때는 가장 나중에 사용할 것을 뽑는 것이 최적이다. 반대로 가장 나중에 사용할 용품이 아닌 것을 뽑았다고 치면, 그 전기용품 차례가 왔을 때 어차피 기존 것을 하나 뽑고 새로 꽂아야 하기 때문이다.

반응형

---

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

const int MAX = 101;
int N, K, cnt;
int schedule[MAX], multitap[MAX];
queue<int> appear[MAX];

int search(int n) {
    int empty = -1;
    int existing = -1;
    int remove_target = -1;
    
    for (int i=0; i<N; i++) {
        if (multitap[i] == n) {
            return i;
        }
        else if (multitap[i] != -1){
            // 가장 나중에 필요한 것을 뽑는다.
            if (remove_target == -1 || appear[multitap[remove_target]].front() < appear[multitap[i]].front()) {
                remove_target = i;
            }
        }
        else {
            empty = i;
        }
    }
    
    if (empty != -1) return empty;
    else return remove_target;
}

int simulate() {
   int cnt = 0;
    
    for (int i=0; i<K; i++) {
        int curr = schedule[i];
        appear[curr].pop();
        
        int pos = search(curr);
        if (multitap[pos] != -1 && multitap[pos] != curr) cnt++;  
        multitap[search(curr)] = curr;
    }
    
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K;
    
    for (int i=0; i<K; i++) {
        cin >> schedule[i];
        appear[schedule[i]].push(i);
    }
    
    for (int i=1; i<=K; i++) appear[i].push(987654321);
    memset(multitap, -1, sizeof(multitap));
    
    cout << simulate();

    return 0;
}