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

1700번: 멀티탭 스케줄링

그리디 알고리즘

OS page replacement policy 중 하나인 Optimal replacement policy 를 적용하는 문제이다.

미래에 어떤 작업을 할 지 다 알고있는 경우이므로 적용이 가능하다 

-> 가장 나중에 사용될 작업을 현재 멀티탭에서 뽑는다 (2021/05/16 update)

 

이 문제에서도 특정 조건이 부합하는지만 알면 언제나 최적의 해를 구할 수 있다

특정 조건을 찾는게 많이 어려웠음..

특정 조건 : ex) 3구짜리 멀티탭이 있고 1,2,3번 기기를 사용중이다. 이제 4번을 써야하는데 1,2,3번 모두 다음에도 써야하기 때문에 어떤 기기를 빼는게 가장 최적 경우인지 모른다!

앞으로 사용할 기기의 순서가 2 1 3 4 2 3 이라면 3번을 빼는게 최선이다

가장 먼저 나오는 순서가 제일 멀리 떨어져 있는 기기를 빼야함.. 말이 좀 이상한데 설명해보자면

1,2,3 이 꼽혀있고 2번기기가 사용되는 순서 중 가장 먼저 사용되는 순서가 1번이다. (나머지 하나는 5번 이라서 비교에서 제외)

1번기기가 사용되는 순서 중 가장 먼저 사용되는 순서는 2번이고, 3번기기가 사용되는 순서 중 가장 먼저 사용되는 순서는 3번이다

이렇게 1,2,3 모두 다음 몇 번째에 사용되는지 알았고 그중 가장 멀리 떨어져 있는 3번 기기를 지금 뽑는게 최선이다!

해당 조건을 찾는게 어렵다! 구현은 어렵지 않은 편이었다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, K, result = 0;
vector<int> UseList, MultiTap;
 
bool inTap(int now){
    for(int i = 0; i < MultiTap.size(); i++){
        if(MultiTap[i] == now) return true;
    }
    return false;
}
 
void plug_out(int useord){
    int fall_idx = 0, mul_idx = 0;
    for(int i = 0; i < MultiTap.size(); i++){
        bool check = false;
        for(int j = useord; j < UseList.size(); j++){
            if(UseList[j] == MultiTap[i]){
                if(fall_idx < j){
                    fall_idx = j;
                    mul_idx = i;
                }
                check = true;
                break;
            }
        }
        if(!check){
            mul_idx = i;
            break;
        }
    }
//    cout << "현재 선택 : " << UseList[useord] << "\n";
//    cout << MultiTap[mul_idx] << " 를 뽑습니다\n";
    MultiTap[mul_idx] = UseList[useord];
    result++;
}
 
void solve(){
    for(int i = 0; i < UseList.size(); i++){
        int now_use = UseList[i];
        if(inTap(now_use)) continue;
        
        if(MultiTap.size() < N) MultiTap.push_back(now_use);
        else plug_out(i);
    }
    
    cout << result;
}
 
void input(){
    cin >> N >> K;
    int temp;
    for(int i = 0; i < K; i++){
        cin >> temp;
        UseList.push_back(temp);
    }
}
 
int main(){
    input();
    solve();
    return 0;
}
 

2020/02/13

0ms