멀티탭 스케줄링

백준 1700번: 멀티탭 스케줄링

아이디어

다음 전기용품이 현재 멀티탭에 꽂혀있지 않은 경우, 꽂혀있는 전기용품중 가장 나중에 다시 등장할 전기용품을 찾아서 걔를 뽑으면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, K;

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

    cin >> N >> K;
    vector<int> v(K);
    for (int i = 0; i < K; i++) {
        cin >> v[i];
    }

    vector<int> cur;
    auto iter = v.begin();
    // 맨 처음 N개 꽂기
    while (iter != v.end() && cur.size() != N) {
        if (find(cur.begin(), cur.end(), *iter) == cur.end()) {
            cur.push_back(*iter);
        }
        iter++;
    }

    int ans = 0;

    while (iter != v.end()) {
        // 다음 전기용품이 멀티탭에 없으면
        if (find(cur.begin(), cur.end(), *iter) == cur.end()) {
            auto k = iter;
            int target = -1;
            for (int i = 0 ; i < N; i++) {
                // 꽂혀있는 전기용품중 가장 나중에 다시 등장할 전기용품을 찾는다
                auto nk = find(iter, v.end(), cur[i]);
                if (nk > k) {
                    k = nk;
                    target = i;
                }
            }
            // 가장 나중에 등장하는 전기용품 뽑고 다음 전기용품 꽂기
            cur[target] = *iter;
            ans++;
        }
        iter++;
    }

    cout << ans;

    return 0;
}

여담

그리디 넘 어렵다.. 당분간 고급 알고리즘은 살짝 접어두고 그리디같은거나 열심히 풀어봐야겠다..