[BOJ 백준] 1700번 멀티탭 스케줄링

문제

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

1700번: 멀티탭 스케줄링

접근

멀티탭에 플러그를 빼는 횟수의 최솟값을 구하는 문제로 그리디 알고리즘(Greedy algorithm)을 통해 문제를 해결할 수 있다.

경우는 세 가지 경우가 있는데

1. 멀티탭에 이미 플러그가 꽂혀있는 경우

2. 멀티탭에 빈자리가 있는 경우

3. 멀티탭이 가득 차 있어 하나를 빼고 플러그를 꽂아야 하는 경우

이렇게 나뉜다.

1, 2번 같은 경우는 기능을 그대로 구현해주면 되지만 3번 같은 경우 어떤 플러그를 뽑는지가 중요하다.

어떤 임의의 플러그가 아무리 많이 꽂을 예정이라 한들 당장 쓰지 않는다면 자리만 차지할 뿐이다. 따라서 이미 꽂혀있는 플러그 중에 가장 늦게 재등장하거나 앞으로 등장하지 않을 플러그를 뽑아주면 된다.

 

코드

// algorithm_study
// BOJ_1700_멀티탭 스케줄링

#include <iostream>
#include <set>

using namespace std;

int main() {
    int n, k, arr[110], answer = 0;
    set<int> s;
    cin >> n >> k;
    for (int i = 0; i < k; i++)
        cin >> arr[i];
    for (int i = 0; i < k; i++) {
        if (s.find(arr[i]) != s.end()) // 멀티탭에 이미 꽂혀있는 경우
            continue;
        else if (s.size() == n && n == 1) { // 멀티탭의 크기가 1인 경우
            s.clear();
            answer++;
        } else if (s.size() == n) { // 멀티탭이 가득 찬 경우
            int count = 0, find[110] = {0};
            for (int j = i + 1; j < k; j++) {
                if (s.find(arr[j]) != s.end() && find[arr[j]] == 0) {
                    count++;
                    find[arr[j]] = 1;
                }
                if (count == n - 1)
                    break;
            }
            for (auto it = s.begin(); it != s.end(); it++) {
                if (find[*it] == 0) {
                    s.erase(*it);
                    break;
                }
            }
            answer++;
        }
        s.insert(arr[i]); // 멀티탭에 플러그를 꽂는다.
    }
    cout << answer;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study