[백준 1700] 멀티탭 스케쥴링 (C++)

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

그리디 Greedy

멀티탭 구의 개수랑 전기용품 사용 순서가 주어지면 플러그를 뺐다 꽂는 횟수의 최솟값을 출력하는 문제

 

접근 방법

우선 꽂혀있는지 확인 (isOn 배열 사용 - 기기별 꽂혀있는지 여부 저장), 멀티탭에 여유공간이 있는지 확인(멀티탭 여유공간 count)

꽂혀있지도 않고, 멀티탭이 모두 사용중인 경우에 대해,

1. 뽑을 기기 번호 (target), 지금 사용 순서와 꽂혀있는 기기의 사용 순서 사이의 거리 (distance) 초기화

2. 꽂혀있는 기기에 대해서 하나씩 스케쥴상의 거리 계산

2-1. 이때 이미 등장했던 기기가 또 나올 수 있기 때문에, 기기가 처음 등장하는 순서와의 거리만 계산해야 하기 때문에, existLater라는 변수를 사용해서 이미 등장했으면 거리를 갱신하지 않도록 했다.

3. 그래서 등장하지 않았거나, 등장하지 않는 기기가 없다면 스케쥴상 거리가 가장 먼 기기를 뺀다.

 

 

오답노트

처음에는 지금 사용할 전기용품이 향후 스케쥴에 등장하는 횟수를 따져서 가장 적게 등장하는 걸 빼는 식으로 했는데,

틀려서, 지금 사용할 것으로부터 지금 꽂혀있는 기기들 각각에 대해서 가장 나중에 등장하는 기기를 빼는 식으로 했다.

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // input
    int N, K;
    cin >> N >> K;
        
    int sequence[100];
    for(int i = 1 ; i <= K ; i++){
        cin >> sequence[i];
    }
    
    // process
    bool isOn[101] = {false,};
    int avail_port = N;
    int switchCnt = 0;
    
    for(int n = 1; n <= K; n++){
        int now = sequence[n];
        //꽂혀있지 않을 때
        if(!isOn[now]){
            if(avail_port > 0){
                // 빈공간있음
                avail_port--;
                isOn[now] = true;
            } else {
                // 빼야됨 - 빈공간 없음
                int target = 1; //뽑을 기기 번호
                int distance = -1; // 꽂혀있는 기기 중 스케쥴에서 가장 거리가 먼 (가장 나중에 사용할) 기기 고르기
                for(int i = 1; i <= K ; i++){
                    if(isOn[i]){
                        // 스케쥴 순서에서 지금 플러그에 꽂혀있는 i와 같은 기기의 거리 알기
                        bool existlater = false;
                        for(int j = n+1; j <= K ; j++){
                            if(sequence[j] == i && !existlater) {
                                existlater = true;
                                if(j-n > distance){
                                    distance = (j-n);
                                    target = i;
                                    break;
                                }
                            }
                        }
                        if(!existlater){
                            target = i;
                            break;
                        }
                    }
                }
                isOn[target] = false;
                isOn[now] = true;
                switchCnt++;
            }
        }
    }
    
    cout << switchCnt;
    
    return 0;
}