백준 1700 멀티탭 스케줄링

작성일 | In |

Problem : 멀티탭 스케줄링

유형 : 그리디

문제 해석

  • 플러그를 빼는 횟수를 최소화 해라

문제 재해석

  • 완전히 OS 스케줄링 belady 알고리즘 구현 문제이다.
  • 최적의 플러그 교체를 한다.
  • 그리디하게 접근한다.

해결 전략

  • 플러그에 남은 공간이 없을경우 가장 나중에 쓰일 플러그를 교체한다.

설계, 구현

  • 전기용품이 사용중인지 확인한다.
  • 사용중이 아니라면, 교체한다.
    • 만약 플러그에 빈공간이 있으면 그냥 꽂는다.
    • 플러그에 빈 공간이 없다면 교체한다.
      • 사용중인것 중 가장 오래 쓰이지 않을 전자기기를 찾는다.
      • 현재 위치부터, 나중에 언제 등장하는지 확인한다.

디버깅

  • algoritm헤더의 find 리턴값을 이상하게 사용하고 있었다.
  • iterator를 리턴 해주니, 포인터로 값에 접근시 당연히 떨어진 거리가 나오지 않는다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

bool _using[102];
vector<int> plug, input_list;
int n, k;
int answer;

void Page_fault(int page, int cur_idx) {
    if (plug.size() < n) {
        plug.push_back(page);
        _using[page] = true;
        return;
    }

    answer++;
    int best_dist = 0;
    int best_idx = 0;
    int best_candidate = plug[best_idx];

    for (int idx = 0; idx < (int)plug.size(); ++idx) {
        int candidate = plug[idx];
        auto exist = find(input_list.begin() + cur_idx, input_list.end(), candidate);

        if (exist == input_list.end()) {
            _using[candidate] = false;
            _using[page] = true;
            plug[idx] = page;
            return;
        }

        int dist = exist - input_list.begin();
        if (best_dist < dist) {
            best_candidate = candidate;
            best_dist = dist;
            best_idx = idx;
        }
    }

    _using[best_candidate] = false;
    _using[page] = true;
    plug[best_idx] = page;
}

void Solve() {
    for (int i = 0; i < k; ++i) {
        int page = input_list[i];

        if (_using[page]) continue;
        Page_fault(page, i);
    }
    cout << answer << "\n";
}

void Input() {
    cin >> n >> k;
    input_list.resize(k);
    for (int i = 0; i < k; ++i) {
        cin >> input_list[i];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • find리턴값을 헷갈리다니.. STL 복습이 필요해 보인다.
  • 논리적으로 설계 하는 것은 빨랐으나, 구현하는데 시간이 걸렸다.
  • 빠른 구현은 많이 하면 늘게 되어있다. 앞으로 문제 좀 많이 풀자