[BOJ] 멀티탭 스케줄링_1700 C++ 풀이

문제

첫 줄에 멀티탭 구멍의 개수 N, 전기 용품의 총 사용횟수 K가 정수로 주어질때, 두 번째 줄에는 전기용품의 이름이 K이하의 자연수로 사용 순서대로 주어진다. 이때 하나씩 플러그를 빼는 최소의 횟수를 출력하는 문제이다.

접근 방법

전기 용품들을 순서대로 schedule 배열을 이용하여 저장하였고 총 3가지 경우로 나누어 프로그램을 구현하였다.

1. 꽂을 플러그 자리가 남아있는 경우
2. 꽂아야 하는 제품이 이미 플러그에 꽂혀져 있는 경우
3. 플러그를 빼고 새로 주어진 제품을 꽂아야 하는 경우

1,2 번의 경우 그냥 넘어갈 수 있지만 3번의 경우 플러그를 빼야한다. 이때 최적의 선택을 하는 그리디 알고리즘을 활용해야 하는데 제일 나중에 사용할 제품을 뽑거나 더이상 사용할 일이 없는 제품을 뽑는게 플러그를 최소로 뽑는데 도움이 된다.

구현

#include<iostream>
#include<vector>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k; // n = 멀티탭 구멍 수, k = 전기 용품 사용 횟수
    int cnt=0;

    cin>>n>>k;
    vector<int> plug(k,0);
    vector<int> schedule(k,0);

    for(int i=0; i<k; i++) cin>>schedule[i];

    for(int i=0; i<k; i++)
    {
        bool plugIn = false;

        for(int j=0; j<n; j++) // 제품이 플러그에 꽂혀 있는 상태인지 확인
        {
            if(plug[j]==schedule[i]) // 제품이 이미 플러그에 꽂혀있는 경우
            {
                plugIn = true;
                break;
            }
        }
        if(plugIn) continue;

        for(int j=0; j<n; j++) // 플러그 자리 남아있는 경우
        {
            if(plug[j]==0)
            {
                plug[j] = schedule[i];
                plugIn = true;
                break;
            }
        }
        if(plugIn) continue;

        int deviceIdx = -1;
        int idx; // 제일 나중에 다시 사용되거나 더이상 사용할 일 없는 제품의 index

        for(int j=0; j<n; j++)
        {
            int lastIdx = 0;

            for(int u=i+1; u<k; u++)
            {
                if(plug[j]==schedule[u]) break;
                lastIdx++;
            }

            if(lastIdx > deviceIdx)
            {
                idx = j;
                deviceIdx = lastIdx;
            }
        }

        cnt++;
        plug[idx] = schedule[i];
    }

    cout<<cnt;
    return 0;
}

BOJ_멀티탭 스케줄링