[PS 백준 - 3.13] 1700번: 멀티탭 스케줄링

문제 정보

백준 1700번 - 바로가기

• 난이도: 골드 1
• 알고리즘: 그리디 알고리즘

---

코멘트

이 문제도 골드치고 수월하게 푼 문제였다.

1. 콘센트 구멍으로 사용할 배열 holes와 전기용품 순서를 나타내는 배열 products를 생성하였다.
2. 먼저 빈 구멍에 전기용품들을 꽂는 과정을 거친다.
3. 빈 구멍을 다 채우면 다른 전기용품들을 채우기 시작한다. 만약 해당 전기용품이 이미 구멍에 꽂혀 있었다면 그대로 idx를 넘기면 되고, 꽂혀 있지 않았다면 꽂힌 것들 중 가장 나중에 다시 쓰일 전기용품의 콘센트를 빼면 된다.

---

소스 코드

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;

    // 먼저 0으로 다 초기화
    int* holes = new int[n];
    for (int i = 0; i < n; i++) holes[i] = 0;

    int* products = new int[k];

    for (int i = 0; i < k; i++) {
        int n;
        cin >> n;
        products[i] = n;
    }

    // 초기화 작업 끝 ---------------------------------------------

    // 1. 처음 빈 구멍에 다 넣기
    int idx = 0;
    int tempIdx = 0;
    int cnt = 0;

    while (true) {
        for (int i = 0; i < idx; i++) {
            for (int j = 0; j < n; j++) {
                if (holes[j] == products[idx]) {
                    idx++;
                    break;
                }
            }
        }
        
        holes[tempIdx++] = products[idx++];
        
        if (tempIdx == n) break;
    }

    // 2. 빈 구멍 채우기 완료! 이제 다른 전기용품들 채우기 시작
    for (; idx < k; idx++) {

        // 1) 만약 꽂혀 있다면 그대로 idx 넘기기
        bool flag1 = false;
        for (int i = 0; i < n; i++) {
            if (holes[i] == products[idx]) { flag1 = true; break; }
        }
        if (flag1) { /*cout << "idx: " << idx << " 넘김" << endl; */continue; }

        
        // 2) 꽂혀 있지 않다면 꽂힌 것들 중 가장 나중에 다시 쓰일 놈을 빼자
        int* distances = new int[n];

        for (int i = 0; i < n; i++) {
            int target = holes[i];
            int j = idx + 1;

            for (; j < k; j++) {
                if (products[j] == target) break;
            }

            distances[i] = j - idx; // 나중에 다시 쓰일 때까지 걸리는 순서
        }

        int max = distances[0];
        int tar = 0;
        for (int i = 0; i < n; i++) {
            if (max < distances[i]) {
                max = distances[i];
                tar = i; // 가장 나중에 쓰일 전기용품 구멍 위치
            }
        }

        holes[tar] = products[idx];
        cnt++;
        //cout << "idx: " << idx << " hole num [" << tar << "] = " << holes[tar] << endl;
        delete[] distances;
    }

    cout << cnt;

    delete[] holes;
    delete[] products;
}