[백준] 1700번: 멀티탭 스케줄링 / C++

✏️ 문제 링크

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

1700번: 멀티탭 스케줄링

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

1. 멀티탭에 이미 꼽혀 있는 경우:

    1-1. 계속 진행

2. 멀티탭에 꼽혀있지 않은 경우

    2-1. 멀티탭이 꽉 차지 않은 경우

        2-1-1. 바로 꼽는다

    2-2. 멀티탭이 꽉 차있는 경우 

        2-2-1. plug별 가장 나중에 사용될 것 혹은 아예 사용되지 않을 아이를 고른후 뽑느다. 

 

 

✏️ 문제 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

vector<int> used(101, false);
vector<int> order;
vector<int> plug;
int N, K;

int get_min(int idx){
    //return index for removing in plug
    int r=0; 
    for(int i=0; i<plug.size(); i++){
        int t=100;
        for(int j=idx; j<order.size(); j++){
            if(order[j]==plug[i]){// 가장 나중에 사용될 아이
                t=j;
                break;
            }
        }
        // 발견되지 않은 경우
        if(t==100) return i;
        else r=max(r, t);
    }
    for(int i=0; i<plug.size();i++){
        if(plug[i]==order[r])
            return i;
    }

}

int main()
{
    int answer=0;
    cin>>N>>K;
    for(int i=0; i<K; i++){
        int in; cin>>in;
        order.push_back(in);
    }
    
    for(int i=0; i<order.size(); i++){
        int cur=order[i];
		//이미 사용중인 경우 
        if(used[cur]){
            continue;
        }else{
        	//플러그가 꽉찬 경우
            if(plug.size()>=N){
                answer++;
                int low=get_min(i);
                
                used[plug[low]]=false;
                plug.erase(plug.begin()+low);
            }
            plug.push_back(cur);
            used[cur]=true;
        }
    }
    cout<<answer<<"\n";
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐