[백준] 1700번 멀티탭 스케줄링

문제: 1700번: 멀티탭 스케줄링

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
//#include <bits/stdc++.h>

using namespace std;

int a[105]; // 전기용품의 사용 순서
bool power[105]; // 해당 전기용품이 멀티탭에 꽂혀 있는지 여부

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

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
        cin >> a[i];

    int ans = 0;
    int cnt = 0; // 멀티탭에 꽂혀 있는 전기용품 개수
    for (int i = 1; i <= k; i++) {
        int cur = a[i];
        if (power[cur]) continue; // 이미 꽂혀 있으면 넘어감
        // 멀티탭에 자리가 남으면 그냥 꽂음
        if (cnt < n) {
            power[cur] = true;
            cnt++;
        }
        else {
            // 멀티탭에 꽂혀 있는 전기용품 중 a 에서 앞으로 가장 빨리 나올 위치를 이름과 함께 저장
            vector<pair<int, int>> idx;
            for (int x = 1; x <= k; x++) {
                if (!power[x]) continue;
                bool vis = false;
                for (int y = i + 1; y <= k; y++) {
                    // i+1 이후에 언제 다시 사용될지 확인
                    if (a[y] == x) {
                        idx.push_back({ y,x }); // (다음 사용될 위치, 기기 번호)
                        vis = true;
                        break;
                    }
                }
                if (!vis) idx.push_back({ k + 1, x }); // 앞으로 사용되지 않을 경우 k+1 로 처리
            }
            // 다음 사용될 위치를 기준으로 내림차순 정렬
            // 가장 늦게 사용되는 거 먼저 뽑으면 됨
            sort(idx.begin(), idx.end(), greater<pair<int, int>>());

            int target = idx[0].second;

            power[target] = false; ans++;
            power[cur] = true;
        }
    }
    cout << ans;

    return 0;
}

 

아.. 아직 골드 1 문제는 무리인 것 같다. 너무 어렵다;;

 

1시간 반 동안 문제 풀어보다가 진짜 모르겠어서 결국 답안지를 봤다;; 멀티탭이 꽉 차서 하나를 뽑아야 할 때 기준을 어떻게 설정 해야 할 지 감이 잘 안 왔는데 보니까 현재로부터 가장 늦게 나오는 애를 뽑아야 하는 거였다.

 

멀티탭을 가장 오랫동안 차지할 수 있는 기기를 유지해야 한다.그래야 최대한 적은 횟수로 교체하면서 필요한 기기들을 꽂을 수 있음.즉, 현재 꽂혀 있는 기기 중에서 "가장 나중에 다시 사용되거나, 더 이상 사용되지 않는 기기"를 선택해서 제거하는 것이 최적의 선택이다.이렇게 하면 가까운 미래에 당장 필요한 기기들은 유지하면서, 최대한 늦게까지 교체를 미룰 수 있음.

 

;;; 아 너무 어려워서 내일 다시 한 번 풀어봐야 할 것 같다 ㅠ_ㅠ;;;;