[BeakJoon 1700] 멀티탭 스케줄링

안녕하세요. 이번 포스팅에서는 백준 1700번 멀티탭 스케줄링 문제를 풀어보도록 하겠습니다.

 

해당 문제는 

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

1700번: 멀티탭 스케줄링

 

위 링크에서 확인하실 수 있습니다.

 

 

그리디 문제이고, 멀티탭에서 어떠한 원소를 뽑는 것이 최선일까를 생각하는 것이 어려운 문제입니다.

 

우선 직관적으로 생각했을 때, 당연히 이후 순번에서 등장하지 않는 멀티탭을 제거하는 것이 제일 중요합니다.

 

2 7

2 3 2 3 1 2 7

 

이러한 입력이 주어졌을 때 2 3 2 3 까지는 멀티탭에 2 3이 입력된 상태로 진행됩니다. 하지만 1이 주어진 순간 2와 3 중 하나를 제거해야 합니다.

 

이때 당연히 이후에 추가되지 않는 3을 제거하는 것이 최선의 선택입니다.

 

2 9

2 3 2 3 1 2 7 3 5

 

입력이 위와 같이 들어온다면 어떻게 될까요?

 

이경우에는 2와 3 모두 이후에 등장하기 때문에 어떠한 규칙이 필요합니다.

 

 

이때 2가 이후에 등장하는 순번보다, 3이 등장하는 순번이 이후이므로 3을 제거해주시면 됩니다. 가장 늦게 등장하는 것을 제거하는 것이 그 순간에 최선의 선택이기 때문입니다.

 

추가로 운영 체제론에 

페이지 교체 전략 중 최적(Optimal) 페이지 교체 방법이 있습니다. 바로 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 전략입니다. 

(https://www.geeksforgeeks.org/page-replacement-algorithms-in-operating-systems/)

 

이는 실제로 구현할 수 없는 전략인데, 그 이유는 이후의 어떠한 페이지를 사용할지 현재의 시점에서 알 수 없기 때문입니다. 하지만 이 문제는 이후의 어떠한 전기용품이 사용될 지 주어지기 때문에 위 전략을 사용할 수 있습니다.

 

요약하자면, 

1. 현재 tab에 있다면, continue

2. 현재 tab에 없다면, 

2-1) 이후에 존재하지 않는 전기용품이라면 -> 선택

2-2) 이후에 존재하지 않는 전기용품이 없다면 -> 처음 등장 시점이 가장 먼 전기용품을 선택

2-3) 선택된 전기용품을 현재 tab에서 지우고, 새로운 용품 추가

3. 1~2 반복

 

으로 해결하시면 됩니다.

 

<소스 코드>

#include<bits/stdc++.h>
using namespace std; 
int n, k, res;
int findEraseNo(vector<int>& tab,vector<int>& v,int idx) {
	int ret = 0, longestIdx=0;
	for(int i = 0; i < tab.size(); i++) {
		int cur = tab[i];
		auto findIdx = find(v.begin()+idx, v.end(), cur);
		if(findIdx == v.end()) return i;
		
		int findPos = (int) (findIdx - v.begin());
		if(findPos > longestIdx) {
			longestIdx = findPos; ret = i;
		}
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);	
	cin >> n >> k;
	vector<int> v(k), tab;
	
	for(int i = 0; i < k; i++) cin >> v[i];
	
	for(int i = 0; i < k; i++) {
		if(find(tab.begin(), tab.end(), v[i])==tab.end()) {
			if(tab.size() < n) {
				tab.push_back(v[i]);
			} else if(tab.size()==n) {
				int eraseNo=findEraseNo(tab, v, i);
				tab.erase(tab.begin()+eraseNo);
				tab.push_back(v[i]);
				res++;
			}
		}
	}
	
	cout << res << "\n";
 	return 0; 
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.