[Algorithm/C++17] 백준 1700 멀티탭

문제

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

1700번: 멀티탭 스케줄링

풀이 방법

멀티탭 구멍의 개수 N과 전기용품의 총 사용 횟수 K가 주어진다. 그 뒤 사용 순서대로 K 이하의 수가 K만큼 주어진다.

쉽게 말해서 두 번째 줄 i번째 입력의 값은 i에 사용하는 기기라는 뜻이다.

페이지 교체 알고리즘이 떠오르는 문제이며, 교체 횟수가 최소가 되는 알고리즘은 바로 가장 오랫동안 사용되지 않는 페이지를 교체하는 최적(Optimal) 알고리즘이다. 다만 실제로는 앞으로 사용할 페이지를 알 수 없기 때문에 사용할 수 없다.

이 문제에서는 전체 사용 순서가 주어져 있기 때문에 최적 알고리즘으로 풀이가 가능하다.

페이지를 전기용품으로 보고, 멀티탭에 꽂은 전기용품 중 앞으로 가장 오랫동안 사용하지 않는 전기용품을 뽑아 사용할 전기용품을 꽂으면 된다.

• 멀티탭이 비어있을 경우 사용할 전기용품을 그냥 꽂으면 된다.
• 사용할 전기용품이 멀티탭에 이미 꽂혀있을 경우는 특별히 처리해줄 것이 없다.
• 멀티탭이 꽉 차 있을 경우 꽂혀있는 전기용품 중 앞으로 가장 오랫동안 사용하지 않는 전기용품을 뽑고, 사용할 전기용품을 꽂는다.

코드

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
    int n, k, t;
    scanf("%d %d", &n, &k);
    vector<int> order; // i에 사용하는 기기번호
    vector<int> plug(n, 0); // i번 플러그에 사용중인 기기 번호
    for(int i=0; i<k; i++)
    {
        scanf("%d", &t);
        order.push_back(t);
    }
    int answer = 0;
    for(int i=0; i<k; i++)
    {
        // 이미 꽂아놓은 기기인지 확인한다.
        bool use = false;
        for(int j=0; j<n; j++)
        {
            if(order[i] == plug[j])
            {
                use = true;
                break;
            }
        }
        if(use) continue;
        // 비어있는 플러그가 있으면 거기에 꽂는다.
        bool plugged = false;
        for(int j=0; j<n; j++)
        {
            if(plug[j] == 0)
            {
                plug[j] = order[i];
                plugged = true;
                break;
            }
        }
        if(plugged) continue;
        // 가장 나중에 사용하는 전기용품을 찾는다.
        int idx, max_time = - 1;
        for(int j=0; j<n; j++)
        {
            // 꽂혀있는 전기용품마다 얼만큼 나중에 사용하는지 계산한다.
            int time = 0;
            for(int next=i+1; next<k; next++)
            {
                if(plug[j] == order[next]) break;
                time++;
            }
            // 가장 나중에 사용하는 전기용품의 번호를 저장한다.
            if(time > max_time)
            {
                idx = j;
                max_time = time;
            }
        }
        // 전기용품을 교체한다.
        answer++;
        plug[idx] = order[i];
    }
    printf("%d", answer);
    return 0;
}

고찰

문제를 보고 딱 페이징 알고리즘이 떠오르긴 했으나, 실제로 최적 알고리즘을 구현해본 적이 없어서 조금 난감했던 문제이다. 그리디도 맞긴 맞지만 구현에 더 가까운 문제인 느낌이다.