백준 #1700 멀티탭 스케줄링


BOJ #1700 - 멀티탭 스케줄링

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

# 문제 분류

그리디 알고리즘

풀이 접근 방법


  1. 입력을 받을 때 입력 빈도 수를 기록하는 arr 배열과 작동 순서를 기록하는 shd 배열에 각각의 정보를 저장한다.
  2. 그리디 알고리즘을 이용해서 문제를 해결하기 위해서 해야 하는 작업은 다음과 같다.

    a. 멀티탭에 이미 존재하는 경우, 해당 케이스는 건너뛴다.

    b. 멀티탭에 존재하지 않는 경우 멀티탭에 빈 공간이 있다면 넣고, 아니면 다음 과정을 수행한다.

    c. 멀티탭에 있는 것 중 ( 앞으로 쓰지 않는 것 또는 가장 마지막에 사용되는 것 ) 을 빼주면 된다.

멀티탭에 넣어질 때 빈도 수를 기록하는 arr 배열에서의 정보를 1씩 감소시키면 앞으로 사용되지 않을 것을 찾을 수 있다.
또한, 343424 와 같은 순서를 가졌을 때 가장 마지막에 사용되는 것은 4가 아닌 2이므로, 이 점을 조심해야한다.
(3은 첫번째, 4는 두번째, 2는 다섯번째에 처음 사용되므로 2가 제일 뒤에 있는 것이 자명하다)
매번 last 배열을 만들어 첫번째 인덱스를 기록하고, 인덱스가 기록된 것 중 가장 최대인 것을 뽑는 방식으로 코드를 작성했다.

소스 코드


#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

int N, K, arr[110], t, c[110], cnt, shd[110], res;

int main(){
    cin >> N >> K;

    for(int i=1; i<=K; i++){
        cin >> t;
        arr[t]++;
        shd[i] = t;
    }

    for(int i=1; i<=K; i++){
        if(c[shd[i]]){
            arr[shd[i]]--;
        }
        else{
            if(cnt < N){
                c[shd[i]] = 1;
                arr[shd[i]]--;
                cnt++;
            }
            else{
                int p = 0, last[110] = {0}, tmp = 0;
                for(int j=1; j<i; j++){
                    if(c[shd[j]]){
                        if(arr[shd[j]] == 0) p = shd[j];
                    }
                }
                if(p == 0){
                    for(int j=i+1; j<=K; j++) {
                        if(c[shd[j]] && last[shd[j]] == 0) last[shd[j]] = j;
                    }
                    for(int j=1; j<=K; j++){
                        if(last[shd[j]]) tmp = max(tmp, last[shd[j]]);
                    }
                    p = shd[tmp];
                }
                c[p] = 0;
                res++;
                c[shd[i]] = 1;
                arr[shd[i]]--;
            }
        }
    }

    cout << res << endl;

    return 0;
}