BOJ : 1700 멀티탭 스케쥴링

---

[BOJ 1700(G2) 리뷰]

처음에 문제를 보고 '골드2 문제치고는 쉽네..?' 했지만 실제 구현하는 부분에서 엄청나게 애를 먹었다.
머리론 어떻게 하면 답이 나올지 알겠는데 그걸 코드로 옮기는 과정이 조금 복잡했다.

알고리즘은 그리디 알고리즘이다. 항상 최선의 선택을 해야 한다.

• 멀티탭이 비어있다면 비어있는 공간에 먼저 꼽아야 한다.
• 이미 해당 작업이 멀티탭에 꼽혀 있다면 그냥 사용하면 된다.
• 멀티탭은 꽉차있고 새로운 작업을 해야 할때는 가장 나중에 사용되는 작업의 코드를 뽑아야 한다.

위 세가지의 규칙을 만족하며 진행시키면 코드를 빼는 작업을 가장 최소로 만들 수 있다.

내가 애를 먹었던 부분은 가장 나중에 사용되는 작업을 고르는 과정이였다.
set도 사용해보고, 배열하나 더 만들어서 해보고 별의별 짓을 다 했지만 역시 복잡한 문제는 가장 간단하게 생각하면 되는것 같다.

결국 사용한 방법은 사용중인 콘센트를 하나씩 확인하여 해당 작업을 다시 사용하기까지의 횟수를 카운팅하여 가장 count가 높은 콘센트를 뽑도록 코드를 짰더니 해결이 됐다.

(가볍게 문제를 풀고 가려했지만 1시간 30분이 넘게 걸려 오늘 들어야 할 강의가 밀리게 되었다..ㅠ)

---

/*
    20.09.07
    BOJ : 1700 멀티탭 스케쥴링 (https://www.acmicpc.net/problem/1700)
    그리디
*/
#include <bits/stdc++.h>
using namespace std;

int isUsed[101];
int task[101];

vector <int> plug;

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

    int N,K;
    cin >> N >> K;
    


    for (int i = 0; i < K; i++)
    {
        cin >> task[i];
    }

    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < K; i++)
    {
        int input = task[i];

        if (isUsed[input]) continue; //이미 콘센트에 꽂혀있다면 그냥 넘어간다.
        else
        {
            if (cnt != N) //콘센트에 빈 자리가 있다면 먼저 채운다.
            {
                 isUsed[input] = true;
                 plug.push_back(input);
                 cnt++;
                 continue;
            }
        } 

        //기존에 꽂혀있던 걸 뽑고 새로운걸 꼽아야 함 꽂혀 있는 콘센트 중 가장 나중에 사용되는 콘센트를 뽑아야 한다.
        int idx = 0,lastcnt=0;
        for (int j = 0; j < N; j++)
        {
            int count = 0;
            for (int k = i + 1; k < K; k++)
            {
                if (plug[j] == task[k]) break;
                count++;
            }
            if (count > lastcnt)
            {
                idx = j;
                lastcnt = count;
            }
        }
        isUsed[plug[idx]] = 0;
        plug[idx] = input;  
        isUsed[input] = 1;
        ans++;
    }
    cout << ans;
    
}