백준 1700번 멀티탭 스케줄링

🔒[문제 url]

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

🔑알고리즘

$k$개의 플러그를 꽂고자 할때, 마주치는 상황은 다음과같이 3가지이다.
1. 이미 꽂혀있는 경우 : 작업 불필요
2. 빈 구멍이 있는 경우 : 빈 구멍에 플러그를 꽂는다.
3. 빈 구멍이 없는 경우

• 빈 구멍이 없는 경우에는?
  • 가장 오랫동안 쓰지 않을 전기용품을 찾고, 해당 플러그를 뽑은 뒤 새로운 플러그를 꽂는다.

🐾부분 코드

// Already Connected
if (connected[product]) continue;

<이미 꽂혀있는 경우>
작업이 필요하지 않다.

// Hole if Left
bool isLeft = false;
for (int j = 0; j < n; j++)
{
    if (!hole[j])
    {
        isLeft = true;
        hole[j] = product;
        connected[product] = true;
        break;
    }
}
if (isLeft) continue;

<빈 구멍이 있는 경우>
j번째 구멍에 꽂혀있는 플러그가 없다면, 현재 플러그를 꽂는다.

// No hole -> Find the product will not use for longest time
ans++;

int P = 0; // Product's num that will be plugged out.
int H = 0; // Hole's index that will be plugged out.
int longestTime = -1; // if Init with 0, it may pass 'if' statement.
for (int j = 0; j < n; j++)
{
    int temp = 0;
    for (int l = i + 1; l < k; l++)
    {
        // j'th hole's product's time
        if (hole[j] == sequence[l]) break;
        temp++;
    }
            
    if (longestTime < temp)
    {
        longestTime = temp;
        P = hole[j];
        H = j;
    }
}
// Plug the procuct in
connected[P] = false;
connected[product] = true;
hole[H] = product;

<빈 구멍이 없는 경우>
모든 구멍에 꽂혀있는 플러그들에 대하여, 다시 쓰일때까지의 시간이 가장 긴 플러그를 구한다.
(다시 쓰이지 않는 경우도 longestTime값이 가장 커지므로 정상적으로 구해진다.)
이 플러그를 구했다면, 해당 플러그가 꽂힌 위치H와 해당 플러그의 번호P를 기억한 후 새로운 플러그를 꽂는다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
using namespace std;

int n, k;

int sequence[101]{ 0, };
int hole[101]{ 0, };
bool connected[101]{ false, };

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int product; cin >> product;
        sequence[i] = product;
    }
}


void SOLVE()
{
    int ans = 0;

    for (int i = 0; i < k; i++)
    {
        int product = sequence[i];

        // Already Connected
        if (connected[product]) continue;
        
        // Hole if Left
        bool isLeft = false;
        for (int j = 0; j < n; j++)
        {
            if (!hole[j])
            {
                isLeft = true;
                hole[j] = product;
                connected[product] = true;
                break;
            }
        }
        if (isLeft) continue;

        // No hole -> Find the product will not use for longest time
        ans++;

        int P = 0; // Product's num that will be plugged out.
        int H = 0; // Hole's index that will be plugged out.
        int longestTime = -1; // if Init with 0, it may pass 'if' statement.
        for (int j = 0; j < n; j++)
        {
            int temp = 0;
            for (int l = i + 1; l < k; l++)
            {
                // j'th hole's product's time
                if (hole[j] == sequence[l]) break;
                temp++;
            }
            
            if (longestTime < temp)
            {
                longestTime = temp;
                P = hole[j];
                H = j;
            }
        }
        // Plug the procuct in
        connected[P] = false;
        connected[product] = true;
        hole[H] = product;


    }

    cout << ans;
}


int main()
{
    INPUT();

    SOLVE();

}

🥇문제 후기

진짜... 알고리즘 특... 알고나면 쉽다....
그렇지만 알기가 어렵다...
알고나면 왜 알기가 어려웠는지 알기가 어렵다...
정렬도 하고 pq도 쓰고 별별 show를 한 후에 2시간 넘게 걸려서 풀었다..
요약 : 알고알고알기알고알기알기