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

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

1700번: 멀티탭 스케줄링

---

멀티탭 스케줄링 문제는 그리디 알고리즘으로 해결할 수 있습니다.

 

콘센트에 꼽혀 있는 기기 중, 앞으로 사용하지 않거나, 가장 나중에 사용할 기기를 선택하여 현재 사용할 기기와 교체해주면됩니다.

증명은 어렵지만, 믿음으로 푼 문제입니다.

 

알고리즘의 기본 틀은 아래와 같습니다.

1. 멀티탭의 구멍 개수가 기기의 총 사용횟수보다 작은 경우 0을 출력한다.
2. 플러그를 뽑지 않아도 꽂을 수 있는 최대한의 개수를 멀티탭에 꽂는다.
3. 현재 사용할 기기가 멀티탭에 꽂혀 있지 않은 경우
   1. 콘센트에 꽂혀 있는 기기 중 앞으로 사용하지 않거나, 가장 나중에 사용할 기기를 선택한다.
      1. 콘센트에 꽂혀있지만, 앞으로 사용하지 않을 기기의 우선순위가 가장 높다.
         (이러한 기기가 많은 경우 그 중 어떠한 기기를 선택해도 상관없음)
   2. 콘센트에 꽂혀 있는 기기와 현재 사용할 기기를 교체해준다.
4. 더이상 사용할 기기가 없을 때까지 3번을 반복한다.

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int order[101];
int use[101];

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

    int n, k; cin >> n >> k;
    for(int i = 0; i < k; i++) cin >> order[i];

    if(n >= k){cout << 0 << "\n"; return 0;}    // 멀티탭의 구멍 개수가 기기의 총 사용횟수보다 작은 경우 0 출력
    int o_idx = 0, c_idx = 0;    // 마지막에 꽂힌 콘센트의 idx
    while(c_idx < n){   // 멀티탭에 가능한 모든 기기를 꽂음
        if(find(use, use + n, order[o_idx]) == use + n){
            use[c_idx] = order[o_idx];
            c_idx++;
        }
        o_idx++;
    }
    
    int ans = 0;

    // n은 멀티탭 구멍의 개수, k는 전기 용품의 사용 횟수
    for(int i = n; i < k; i++){
        int cur = order[i]; // 사용할 전기 용품

        if(find(use, use + n, cur) == use + n){ // 사용할 기기가 콘센트에 꼽혀있지 않은 경우
            // 콘센트에 꼽혀 있는 기기 중, 앞으로 사용하지 않거나, 가장 나중에 사용할 기기를 선택
            pair<int, int> m = {INT_MIN, INT_MIN};  // {기기를 다음에 사용할 순서, 기기가 꼽혀있는 콘센트 번호}

            for(int j = 0; j < n; j++){    // j는 콘센트 번호
                pair<int, int> c;    // {다음에 사용할 순서, 기기 번호}
                int pos = find(order + i, order + k, use[j]) - order;

                if(pos == k) c = {INT_MAX, j};  // 앞으로 사용하지 않는 경우
                else c = {pos, j};  // 앞으로 사용하는 경우

                if(c.first > m.first) m = c;    // 더 나중에 사용하는 기기인 경우
            }

            use[m.second] = cur;
            ans++;
        }
    }
    cout << ans << "\n";
}

 

아래는 테스트케이스입니다.

3 12
1 2 3 4 1 2 1 1 1 1 1 3
-> 2

3 4
1 2 3 4
-> 1

3 6
1 2 3 1 2 4
-> 1