[백준 1700번] [그리디] 멀티탭 스케줄링

여러가지 샘플을 만들어가면서 최적해를 구해보면

 

1. 남는 플러그 자리가 있으면 들어간다.

2. 없는 경우 다시 등장하는 것이 이후인 것부터 뽑는다. 만약 다시 등장하지 않는 경우는 해당 값을 INF로 처리해서 최우선적으로 뽑으면 된다.

 

적당히 현재 어느 숫자가 플러그에 꽂혀있는지를 저장해두는 배열을 만들고 관리해주면 된다.

추가적으로 순차적으로 데이터가 들어오고, 앞에서부터 다음 자리의 크기 비교를 해야하는 상황이므로 큐 자료구조를 활용하면 쉽게 풀 수 있다.

 

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
#define INF 987654321

int main(void){
    fastio;
    int n, k;
    cin >> n >> k;
    vector<queue<int> > dp(k + 1);
    queue<int> data;
    
    for(int i = 1; i <= k; i++){
        int temp;
        cin >> temp;
        dp[temp].push(i);
        data.push(temp);
    }

    vector<int> plug(k + 1, 0);

    // 일단 플러그에 다 꽂아둠
    while(n){
        if(!data.empty()){
            int cur = data.front(); data.pop();
            dp[cur].pop();
            if(plug[cur] == 0){
                plug[cur] = 1;
                n--;
            }
        }
        else break;
    }

    int change_num = 0;
    while(!data.empty()){
        int cur = data.front(); data.pop();
        dp[cur].pop();
        // 이미 꼽혀 있는 경우
        if(plug[cur] == 1) continue;
        else{
            int max_index = -1;
            int max_value = -1;
            for(int i = 1; i <= k; i++){
                if(plug[i] == 0) continue; // plug 된 것만 검토
                int cmp;
                // 뒤에 더이상 등장하지 않는 경우
                if(dp[i].empty()){
                    cmp = INF;
                }
                else cmp = dp[i].front();
                if(cmp > max_value){
                    max_value = cmp;
                    max_index = i;
                }
            }
            plug[max_index] = 0;
            plug[cur] = 1;
            change_num++;
        }
    }
    cout << change_num << "\n";
    return 0;
}