백준 1700 : 멀티탭 스케줄링 C++

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

1700번: 멀티탭 스케줄링

 

풀이

1.  새로운 전기용품을 충전하고 싶을때 3가지 경우가 있다

1) 이미 꽂혀 있는 경우

 -> PASS

2) 꽂혀있지는 않지만, 멀티탭에 빈자리가 있음

-> 빈자리에다가 꼽는다

3) 자리가 없다

-> 이 경우가 코딩 필요

 

2. 현재 멀티탭에 꼽혀있는 전자제품 중에 가장 오랫동안 사용 안하는 걸 찾으면 된다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, k;
int schedule[101];
int multiTap[101] = { 0, };

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

    for (int i = 0; i < k; i++)
    {
        bool flag = false;
        //1) 이미 꽂혀 있다면 pass
        for (int j = 0; j < n; j++)
        {
            if (multiTap[j] == schedule[i])
            {
                flag = true;
                break;
            }
        }
        if (flag == true)
            continue;

        //2)빈칸이 있으면 꼽아
        for (int j = 0; j < n; j++)
        {
            if (multiTap[j] == 0)
            {
                multiTap[j] = schedule[i];
                flag = true;
                break;
            }
        }
        if (flag == true)
            continue;


        //3) 빈칸 필요
        int last_need = -1; // 가장 늦게 다가올 차례
        int index = -1; // 뺄 멀티탭 자리
        for (int j = 0; j < n; j++)
        {
            int tmp = 0;
            for (int t = i+1;t < k; t++)
            {
                if (schedule[t] == multiTap[j])
                {
                    break;
                }
                tmp++;
            }
            if (tmp > last_need)
            {
                last_need = tmp;
                index = j;
            }
        }

        multiTap[index] = schedule[i];
        answer++;

    }
    cout << answer << endl;
}