[C++] 1700번 멀티탭 스케줄링 - 그리디

1700번 멀티탭 스케줄링

 

1. 문제

• 생략

2. 재정의

• 생략

3. 실수한 점, 개선할 점

• 생략

4. 해결 방법

• 생략

<코드>

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_K = 101;
const int MAX_N = 101;
const int INF = 987654321;

int N, K;
vector<queue<int>> elec(MAX_K);
int order[MAX_K];
int chg[MAX_N];

void input() {
    cin >> N >> K;
    for(int i=0; i<K; i++) {
        cin >> order[i];
        elec[order[i]].push(i);
    }
    for(int i=1; i<MAX_K; i++)
        elec[i].push(INF);
}

void solve() {
    int res = 0;
    
    for(int i=0; i<K; i++) {
        int now = order[i];
        bool flag = false;
        
        int M = 0;
        int M_value = -2;
        
        for(auto x: chg)
            if(x == now)
                flag = true;
                
        for(int j=0; j<N; j++) {
            if(elec[chg[j]].empty()) {
                M = j;
                break;
            }
            if(M_value < elec[chg[j]].front()) {
                M = j;
                M_value = elec[chg[j]].front();
            }
        }
        
        elec[now].pop();
        if(flag)
            continue;
        else {
            if(chg[M])
                res++;
            chg[M] = now;
        }
    }
    
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

 

<문제 바로가기>

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

1700번: 멀티탭 스케줄링