백준 1700 - 멀티탭 스케줄링

문제

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

1700번: 멀티탭 스케줄링

 

풀이

구멍이 비어 있는 경우 그 구멍을 사용한다. 모든 구멍을 사용 중이면 꽃혀 있는 것들 중에서 가장 나중에 사용하는 것을 빼고 그 자리에 새 것을 꼽는다. 교체해야 할 때 사용 빈도가 가장 적은 것을 빼려 했는데 틀린 알고리즘이었다.

 

코드

#include <iostream>
 
using namespace std;
 
int N, K;
int order[101];
int hole[101];
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N >> K;
 
    for (int i = 1; i <= K; i++)
    {
        cin >> order[i];
    }
 
    for (int i = 1; i <= K; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            // 구멍이 비어 있는 경우
            if (!hole[j])
            {
                hole[j] = order[i];
                break;
            }
            else
            {
                // 이미 사용중이면 넘어간다
                if (order[i] == hole[j])
                {
                    break;
                }
                // 다음 구멍을 검사한다
                if (j != N) continue;
 
                // 멀티탭에 꽃혀 있는 것 중에서 가장 나중에 사용하는 것을 고른다.
                int change, val = -1;
                for (int k = 1; k <= N; k++)
                {
                    int term = 0;
                    for (int l = i + 1; l <= K && order[l] != hole[k]; l++) term++;
                    if (term > val)
                    {
                        val = term;
                        change = k;
                    }
                }
                // 가장 나중에 사용하는 것을 뽑는다.
                hole[change] = order[i];
                result++;
            }
        }
    }
 
    cout << result;
 
    return 0;
}