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

 

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

요즘 그리디에 너무 약해서 그리디 문제를 풀던 중 골머리를 앓았던 문제에 대하여 포스팅합니다.

이 문제는 각 전기용품의 사용 순서가 k개 주어지고 멀티탭이 n개 구멍이 있을때 주어진 전기용품을 순서대로 사용하면서 플러그를 뽑는 최소횟수 구해야 합니다.

가장 처음에 든 생각은 멀티탭을 모두 사용하고 있으며 다음 전기용품이 멀티탭에 꼽혀있지 않은 경우, 즉 플러그를 하나 뽑아야되는 시점에서, 꼽혀있는 전기용품 중 앞으로 사용횟수가 가장 적은 전기용품의 플러그를 뽑아야 한다였습니다.

틀렸습니다

2 15

3 1 2 1 2 1 2 1 2 3 3 3 3 3 3 

이러한 반례가 존재하더군요. 처음 3을 뽑고 나중에 2나 1을 뽑는 2가 답이였지만 남은 횟수로 뽑게된다면 답이 7이 나오더군요.

위의 반례를 해결할 수 있는 규칙을 찾다보니 2가지 규칙이 나왔습니다.

1. 더이상 사용하지 않는 전기용품을 뽑자.

2. 만약 멀티탭을 사용중인 전기용품 중 1번 경우가 없다면, 가장 나중에 사용되는 전기용품을 뽑자.

1번 규칙의 경우 당연한 얘기고,

2번 규칙의 경우 가장 나중에 사용하는 전기용품을 뽑지않고 그 전에 사용될 전기용품을 뽑으면 해당 전기용품을 사용하기 위하여 다른 전기용품의 플러그를 한번더 뽑아야 합니다.

저는 큐를 사용하여 간단하게 처리했습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <string>
#include <queue>
using namespace std;
int n, k;
int arr[101];
queue<int> v[101];
int inQ[101] = { 0, };
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		cin >> arr[i];
		v[arr[i]].push(i);
	}
	int ans = 0;
	int _size = 0;
	for (int i = 1; i <= k; i++) {
		int s = arr[i];
		if (inQ[s]) {
			v[s].pop();
			continue;
		}
		if (_size == n) {
			int _idx = -1;
			for (int j = 1; j <= k; j++) {
				if (inQ[j]) {
					if (v[j].empty()) { // ... 1번 규칙
						_idx = j;
						break;
					}
				}
			}
			if (_idx == -1) { // ... 2번 규칙
				int _last = -1;
				for (int j = 1; j <= k; j++) {
					if (inQ[j] && _last < v[j].front()) { 
						_last = v[j].front();
						_idx = j;
					}
				}
			}
			_size -= 1;
			inQ[_idx] = 0;
			ans += 1;
		}
		_size += 1;
		inQ[s] = 1;
		v[s].pop();
	}
	cout << ans;
	return 0;
}