BOJ 1700 멀티탭 스케줄링

 

BOJ 백준 1700 C++

멀티탭 스케줄링

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

 

 

1) 처음에는 N개를 채울 때까지 order[]를 차례대로 진행한다

 

2) N개를 모두 꽂으면, 꽂혀 있는 것 중 제거할 것을 선택해야 한다.

 

case 0. 꽂혀 있는 것을 확인하여, 앞으로 사용 안 하는 것 있으면 제거

case 1. 꽂혀 있는 것들을 확인했는데, 모두 사용될 예정이면 (case0에서 조건 걸리지 않으면), 가장 나중에 사용될 것을 제거

[현재 order의 다음 순서(i+1) ~ 순서의 끝(K)]을 for 돌면서 아래 조건을 확인한다.

if(res[order[j]][0]>0 && res[order[j]][1]==1 && !check[order[j]])

-> (앞으로 사용될 것 && 사용하는 중 && 확인 안 했으면)

-> 제거할 플러그이다 (order[i]순서로 진행하기 때문에 가장 나중에 사용할 플러그를 선택할 수 있음)

 

3) 제거 할 플러그를 선택했으면, res[removeNum][1]을 0(false)로 변경하고

새 플러그를(order[i])를 꽂는다. (res[order[i]][0]는 1 감소, res[order[i]][1]는 true) 

 

 

/**
 * 200616
 * BOJ 1700 멀티탭 스케줄링
 * greedy 구현
 * */

#include <iostream>
using namespace std;

int order[105]; // 입력 순서
int res[105][2]; // 각 번호당 사용 횟수, 현재 꽂혀있는지 여부

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N, K;
    cin >> N >> K;

    for(int i=1; i<=K; i++){
        int x;
        cin >> x;
        
        order[i] = x;
        res[x][0]++;
    }

    int fillMultiTap = 0;
    int ans = 0;
    for(int i=1; i<=K; i++){
        // 처음 N회는 그냥 꽂는다
        if(fillMultiTap<N){
            res[order[i]][0]--;
            if(res[order[i]][1]==0){ // 안 꽂혀 있으면
                fillMultiTap++;
                res[order[i]][1]=1;
            }        
        }

        else{ // N회 지나면
            // 이미 꽂혀있으면 pass
            if(res[order[i]][1]==1) {
                res[order[i]][0]--;
                continue;
            }

            /** 하나 빼야하는 경우
             * case 0. 꽂혀 있는 것 중 앞으로 사용 안하는 것 있으면 제거
             * case 1. 꽂혀 있는 것들이 모두 사용 될 예정이면,  
             *      가장 나중에 사용 될 것을 제거
            */

            int removeNum=0;
            bool caseFlag=true;
            // case 0
            for(int j=1; j<=K; j++){
                if( res[order[j]][0]==0 && res[order[j]][1]==1 ){
                    removeNum = order[j];
                    caseFlag=false;
                }
            }
            
            // case 1
            if(caseFlag){
                int tmp = 0;
                bool check[105];
                for(int i=1; i<=K; i++) check[i]=false;
                for(int j=i+1; j<=K; j++){
                    if(res[order[j]][0]>0 && res[order[j]][1]==1 && !check[order[j]]){
                        if(tmp >= N) break;

                        removeNum = order[j];
                        check[order[j]]=true;
                        tmp++;
                    }
                }
            }

            res[removeNum][1]=0; // 제거

            res[order[i]][0]--; // 꽂는다
            res[order[i]][1]=1;
            ans++;
        }
    }

    cout << ans << '\n';
}