[그리디 #15] BOJ 1700 - 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

 

1차 시도

너무 간단하게 생각했다.

 

뒷 부분 중 가장적게 사용되는 것을 뽑는 것으로 진행해버렸다.

당연히 반례가 존재한다.

 

3 15

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

 

위 반례에서 3과 2를 꼽고나서 1이 나왔을 때, 3이 2보다 많이 사용되므로 2를 뽑게된다..

 

 

정답

"가장 나중에 사용되는 것을 우선적으로 뽑자!" 라는 것을 다시 생각해보았다.

 

나중에 사용된다는 것이 현재 꼽아져있는 플러그 중 가장 나중에 사용되는 것을 우선 뽑자라는 의미이다.

 

이를 어떻게 구현할지 많이 생각해보았는데, 큐를 이용하면 좋겠다고 생각했다.

큐에 다음에 오는 index를 저장하면, front()를 통해 쉽게 다음에 사용될 순서를 알 수 있다.

이를 통해 알고리즘은 다음과 같이 정리할 수 있다.

 

1. 큐에 i 번째 물건의 사용 순서를 모두 넣는다.

2. 사용을 하면서, 코드가 모두 사용중일 경우 가장 나중에 사용될 물건을 찾는다.

   2-1. 현재 사용중인 물건을 for문으로 돌면서 front()가 가장 큰 물건을 선정한다.

3. 가장 나중에 사용되는 물건과 현재 사용할 물건을 바꾸고, 현재 사용할 물건의 큐를 pop한다.(사용을 했기 때문에 사용순서 최신화)

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int seq[101];
bool curr[101];

queue<int> q[101];
int n, k;

int findLast() {
	int res = 0;
	int res_idx = 0;
	for (int i = 1; i < 101; i++) {
		if (curr[i] == true) {
			if (q[i].size() == 0) {
				res_idx = i;
				break;
			}
			else if (q[i].size()>0 && res < q[i].front()) {

				res = q[i].front();
				res_idx = i;
			}
		}
	}
	return res_idx;;
}

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

	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> seq[i];
		q[seq[i]].push(i);

	}

	int cnt = 0;
	int plug = 0;
	for (int i = 0; i < k; i++) {
		if (plug < n && curr[seq[i]] == false) {
			curr[seq[i]] = true;
			q[seq[i]].pop();
			plug++;
		}
		else if(plug >= n && curr[seq[i]] == false) {
			int last = findLast();
			
			// 교체
			if(!q[seq[i]].empty())
				q[seq[i]].pop();

			curr[seq[i]] = true;
			curr[last] = false;
			cnt++;
		}
		else {

			if (!q[seq[i]].empty())
				q[seq[i]].pop();
		}
	}
	
	cout << cnt;
}

 

입력 순서와 for을 돌때 사용하는 i가 너무 헷갈림...(seq[i]와 i)