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

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

 

골드1 치곤 조금 쉽다고 느낀 문제이다.

처음엔 DP를 생각했다. 하지만 알고리즘 분류를 보니 그리디였다. DP로 점화식이나 규칙을 찾아볼 때 이전의 값을 사용하는 낌세가 보이지 않고, 상태를 계속 변경하면서 체크해야하면 그것은 DP가 아님을 인지하고 빠져나와야하는데 실력이 너무너무너무 부족하다. 하,,

 

그리디로 넘어와서 멀티탭에 꽂아져있거나, 자리가 있으면 괜찮지만 자리가 없으면 무엇을 뽑아야할지 정해야한다.

 

여기서 난 처음에 2, 4, 5 가 꽂혀있다고 할 때 남은 스케줄 중 2의 개수, 4의 개수, 5의 개수 중 가장 개수가 적은 것을 뽑는 알고리즘을 작성했다. 합리적으로 보이나 반례가 있었다. 

 

만약 

 

3 2 3 4 4 4 5 5 5

 

라고 한다면, 알고리즘에 의해 2가 뽑히고

3 4 5 가 될 것이고 남은 2 3 4 4 4 5 5 5 에서 또 3을 뽑을 것이다.

 

2 4 5 가 될 것이고 남은 3 4 4 4 5 5 5에서 또 3을 위해 2를 뽑는다! 그래서 총 3번 이상 코드를 뽑게된다.

 

만약 처음 2를 뽑지 않고 5를 뽑았다면?

 

2 4 3 이 될 것이고 2,3,4를 모두 넘어간 후 5가 나왔을 때 한번 코드를 뽑게 되어 2번 코드를 뽑는 것으로 스케줄을 완성할 수있다.

 

즉, 얼마나 많이 남아있느냐가 중요한게 아니라 가장 늦게 다시 사용하거나 다시 사용하지 않을 코드를 뽑아야 정답이다.

 

이것을 저장하기 위해 난 각 기기마다 우선순위큐를 만들어 기기가 나오는 좌표를 넣어두고 각 기기를 코드에 꽂을 때 마다 pop하여 그 다음 좌표가 우선순위큐에서 나오도록 하였다. (지금 생각해보니까 우선순위큐일 필요가 없네..?)

 

아무튼, 이정도 문제는 충분히 코딩테스트 마지막 문제나 마지막 전번 문제로 나올 수 있을 것 같다. 자력 솔빙을 못해서 아쉽다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;

const int MAX = 101;

vector<int> plugs;
vector<int> things(MAX);
priority_queue<int> pq[MAX];

int answer = 0;
int main(){
	int N, K;

	cin >> N >> K;

	for(int i = 0; i < K; i++){
		cin >> things[i];

		pq[things[i]].push(-i); // 이 플러그가 등장하는 순서
	}

	for(int i = 0; i < K; i++){
		int space = plugs.size();

		pq[things[i]].pop();

		if(find(plugs.begin(), plugs.end(), things[i]) != plugs.end()){ // 이미 꽂혀있음
			continue;
		}else if(space < N){
			plugs.push_back(things[i]);
		}else{
			answer++;
			int minIdx = 100000000;
			int maxValue = 0;
			for(int j = 0; j < plugs.size(); j++){
				if(pq[plugs[j]].empty()){
					minIdx = j;					
					break;
				}
				else if(maxValue < -pq[plugs[j]].top()){
					maxValue = -pq[plugs[j]].top();
					minIdx = j;
				}
			}
			plugs[minIdx] = things[i];
		}
	}

	cout << answer << '\n';

	return 0;
}