[BOJ] 1700 멀티탭 스케줄링

1700 문제보기

문제의 조건

멀티탭 구멍의 개수가 $N$개이고, 전기 용품들(최대 $K$개만큼 있다.)을 총 $K$번 사용할 때, 멀티탭에서 플러그를 빼는 횟수를 최소화 하는 것이 목적.

접근 방식

먼저, 플러그를 뽑는 방식을 최소화 하려면 어떻게 해야하나? 에 대해서 생각할 수 있는 여러 방법을 떠올려본다.

1. 가장 먼저 쓴 플러그를 뽑는다.
2. 앞으로 가장 적게 쓰일 플러그를 뽑는다.
3. 꽂혀 있는 플러그 중, 가장 나중에 나오는 플러그를 뽑는다.

3가지 방법에 대해서 예제의 테스트 케이스를 돌려본다.

2 7
2 3 2 3 1 2 7

1번, 가장 먼저 쓴 플러그를 뽑을 경우 예제의 입력에 대한 출력이 최적이 아니다.
2번, 3번의 경우 예제 출력이 정확하게 나오지만 아직 확실하게 알 수 없다. 혹시 예외 사항이 어떤 것이 있을까 테스트케이스를 직접 만들어 본다.

case #2
3 8
1 2 1 4 1 2 2 2

case #3
3 9
1 2 3 4 2 1 3 3 2

#include <iostream>
using namespace std;
int main(){
    return 0;
}

각각 2번과 3번의 접근법에 대한 예외로, 4를 꽂을 때, 각각의 조건에 따라 플러그를 뽑지만, 바로 다음에 뽑은 플러그를 다시 사용해야 하기 때문에 최적해를 구해내지 못한다. 그러므로 2, 3 역시 올바른 접근법이 아니다.

위의 2번과 3번을 접근하면서 내가 뽑은 플러그가 바로 다음에 나오게 되는 문제가 있었다. 그러면, 현재 뽑아야 하는 플러그를 결정할 때, 뽑은 이후에 처음 사용하는 시점이 가장 늦은 플러그 를 뽑는 것이 어떨까?
다음과 같은 방식을 사용하면 만들어둔 테스트케이스에 대해서는 모두 최적해를 출력함을 알 수 있다. 현재를 기준으로 처음 사용하는 시점이 가장 늦은 것을 찾는 것이기 항상 최적이기 때문에, 그리디 알고리즘을 사용하여 풀 수 있다.
$K$개의 시점에서 각각의 플러그 $N$개에 대해 다음에 나오는 시점을 찾아주어야 하므로 시간복잡도는 $O(NK^2)$ 가 된다.

코드

	#include <bits/stdc++.h>
	#include <unordered_set>
	using namespace std;
	typedef pair<int, int> pii;
	int main() {
	int n, k;
	cin >> n >> k;
	vector<int> seq(k + 1);
	unordered_set<int> plug;
	for (int i = 0; i < k; i++) {
	cin >> seq[i];
	}
	int ans = 0;
	for (int i = 0; i < k; i++) {
	if (plug.find(seq[i]) == plug.end()) {
	if (plug.size() >= n) {
	int unplug = 0;
	vector<pii> next_use(plug.size());
	for (auto it = plug.begin(); it != plug.end(); it++) {
	//find plug usage;
	int number = *it;
	bool f = false;
	for (int j = i+1; j < k; j++) {
	if (seq[j] == number) {
	next_use.push_back({ j,seq[j] });
	f = true;
	break;
	}
	}
	if (!f) {
	next_use.push_back({ 101 , number });
	}
	}
	sort(next_use.begin(), next_use.end());
	unplug = next_use[next_use.size() - 1].second;
	plug.erase(unplug);
	ans++;
	}
	plug.insert(seq[i]);
	}
	}
	printf("%d", ans);
	return 0;
	}

view raw boj_1700.cpp hosted with ❤ by GitHub

엉망코드 ㅠㅠ
unordered_set은 굳이 안써도 되는데 그냥 잘 안쓰던 STL 문법이라 사용해보고 싶어서 사용했다.

unordered_set <int> plug
plug는 현재 꽂혀있는 플러그들의 집합이다.
next_use 는 콘센트에 꽂혀있는 플러그가 언제 처음으로 다시 사용되는지 저장해주는 vector이다.
plug.size() >= n 인 경우, 각각의 꽂혀있는 플러그를 살펴보며 플러그가 언제 처음 나오게 되는지 살펴본다. 만약, 이후에 한번도 나오지 않는다면 INF 값을 주도록 한다.
이후 next_use를 정렬한 후, 가장 뒤에 있는 값을 선택해주면, 이후 사용되지 않거나 가장 나중에 다시 사용되는 플러그이다.
따라서 콘센트에서 이 플러그를 제거해주면 된다.