4주차(그리디) - [C++]백준1700 멀티탭 스케줄링

27 Mar 2022 in Study on Algorithm

백준1700 멀티탭 스케줄링 링크

문제

예제 입력

---

코드

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

int N, K;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    cin >> N >> K;
    vector<int> plug(N);
    vector<int> schedule(K);

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

    int result = 0;
    for (int i = 0; i < K; i++)
    {
        bool check = false;
        //해당 기기가 있는지 확인
        for (int j = 0; j < N; j++)
            if (plug[j] == schedule[i])
            {
                check = true;
                break;
            }
        if (check) continue;

        //비어있는 플러그 확인후에 넣기
        for (int j = 0; j < N; j++)
            if (!plug[j])
            {
                plug[j] = schedule[i];
                check = true;
                break;
            }
        if (check) continue;

        //가장 나중에 다시 사용되거나 앞으로 사용되지 않는 기기 찾고
        int out = 0, device = -1; // 바로 다시 사용하면 최소=0
        for (int j = 0; j < N; j++)
        {
            int cnt = 0;
            for (int k = i + 1; k < K; k++)
            {
                // 조만간 사용됨
                if (plug[j] == schedule[k]) break;
                cnt++;
            }
            // 높을수록 조만간 사용 안하니 바꾸어줘야함
            if (cnt > device)
            {
                out = j;
                device = cnt;
            }
        }
        //기기를 꽂음
        plug[out] = schedule[i];
        result++;
    }

    cout << result;
}

설명

이 문제는 멀티탭에 구멍 갯수와 전자기기 갯수와 그 순서에 따라 변경으로 스케줄링하여 플러그를 빼는 최소의 횟수을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 구멍수와 스케줄를 입력 받아 실행하며 먼저 해당 기기가 있는지 확인해야하는데 그 이유는 처음에 연속으로 2, 2 나올수 있어서 입니다. 그 후에 구멍이 비어 있는지 확인하는데 그래도 자리가 없다면 이제 어느 것을 뽑아야 되는지 현재 상황에 꽂아야 하는 기기 기준으로 다음부터 카운트하여 선정하여 최소의 횟수로 스케줄링합니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과