백준 1700 멀티탭 스케줄링

이 문제는 그리디 알고리즘을 학습하기 위해 푼 문제이다. 처음 접근할 때, 꽂혀있는 멀티탭 중 이후 사용할  횟수가 가장 적은 것을 빼는 것으로 생각했는데, 그것이 아닌 가장 나중에 사용할(즉, 현재를 기준으로 사용할 시기가 가장 나중) 것을 찾아야 하는 것이었다.

정리하자면,

1. 사용 가능 구멍이 존재하면 꽂음

2. 사용할 값이 꽂혀있으면 continue

3. 값을 하나 새로 꽂아야 하는 경우

       1) 꽂혀있는 값들이 언제 다시 사용하는지 체크.

            1-1) 만약 더 이상 사용되지 않는 것이면 그 자리에 새로운 것을 꽂음(다른 멀티탭 확인 안 해도 됨)

            1-2) 모두 이후에 사용된다면, 사용 시기가 가장 나중인 것을 찾아야 함

 

이를 코드로 작성하면 이렇다. 

         

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>tab; //멀티탭
vector<int> order; // 사용할 순서
void insert_tab(int i);
int ans = 0; //바꾼 횟수 
int main() {


	int N, K;
	cin >> N >> K;

	for (int i = 0; i < K; i++) {
		int a;
		cin >> a;
		order.push_back(a);

	}

	if (N >= K) { //멀티탭이 사용할 횟수보다 많으면 바꿀 것 없음

		cout << 0 << endl;
		return 0;
	}

	vector<int>::iterator iter;
	for (int i = 0; i < order.size(); i++) {

		iter = find(tab.begin(), tab.end(), order[i]); //꽂힌것중에 존재하는지 확인
		if (iter != tab.end())continue; //이미 꽂혀있으므로 지나감

		if (tab.size() < N) { // 사용가능할 멀티탭이 남아있으면 꽂음
			tab.push_back(order[i]);
		}
		else {// 하나를 뽑고 새로운 것을 꽂아야함
			insert_tab(i);
		}
	}

	cout << ans << endl;
}

void insert_tab(int i) {

	int before, most_far = 0; //기존 멀티탭값과 가장 나중에 사용되는 멀티탭의 발생위치 
	int new_val = 0;
	int pos = 0; // 해당 값을 언제 다시 사용할지 저장할 변수
	vector<int>::iterator iter;

	for (int m = 0; m < tab.size(); m++) {
		before = tab[m]; //기존의 멀티탭의 값
		pos = 0;
		for (int next = i + 1; next < order.size(); next++) {
			if (order[next] == before) { //이후에 다시 발생함
				pos = next; //pos에 저장 
				break;
			}
		}
		if (pos == 0) { // 더이상 쓰이지 않음
        	tab[m]=order[i];
			ans++;
			return;
		}
		if (most_far < pos) { //더 나중에 사용되는 값을 찾으면
			most_far = pos; //그 위치를 저장하고 
			new_val = m; // 사용할 멀티탭 위치를 지정
		}
	}
	tab[new_val] = order[i]; //멀티탭에 새로운 값 삽입
	ans++;



}

 

매일매일 풀다 보니 조금씩 느는 것 같기도 하다 (아마도,,ㅎㅎ)