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

그리디 알고리즘으로 푸는 문제이다.

 

플러그가 꽂혀있지 않을 경우 사용하는 전기용품 순으로 꽂는다. 이미 플러그에 꽂혀있는 전기용품은 꽂는 작업을 할 필요가 없다. 

 

만약 플러그를 빼야 하는 경우(즉, 멀티탭에 플러그가 모두 사용중인 경우) 가장 나중에 쓰이거나 쓰이지 않을 전기용품의 플러그를 빼야 빼는 횟수를 최소화 할 수 있다. 

 

정리해보면 다음과 같다.

 

• 전기용품 사용 순서대로 빈 플러그에 꽂는다.
• 플러그가 모두 사용 중이며 현재 사용할 전기용품이 플러그에 꽂혀있지 않는 경우 꽂혀있는 플러그 중 가장 나중에 쓰이거나 더이상 쓰이지 않을 전기용품 플러그를 뺀다.

멀티탭에 모든 플러그가 꽂혀있는 경우 N개의 사용순서에서 i번째에 있는 다른 전기용품을 사용해야 한다고 가정하자. 꽂혀있는 전기용품들을 순회돌며 i + 1에서 N까지 추후 또 사용할 전기용품이 존재할때까지 카운트를 샌다. 그 중 카운트가 가장 큰 값의 전기용품 플러그를 빼면 빼는 총 횟수를 최소화 할 수 있다.  

 

코드는 다음과 같다.

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

const int EMPTY = 0;
const int MAX = 100 + 1;

int main()
{
	int multitabCount;
	int multitab[101] = { EMPTY, };
	int schedule[101] = { EMPTY, };
	int scheduleCount;
	vector<int> order;

	cin >> multitabCount;
	cin >> scheduleCount;
	for (int i = 0; i < scheduleCount; ++i)
	{
		cin >> schedule[i];
	}

	int result = 0;
	for (int i = 0; i < scheduleCount; ++i)
	{
		bool pluggedCheck = false;
		for (int j = 0; j < multitabCount; ++j)
		{
			if (schedule[i] == multitab[j])
			{
				pluggedCheck = true;
				break;
			}
		}
		if (pluggedCheck)
			continue;

		for (int j = 0; j < multitabCount; ++j)
		{
			if (EMPTY == multitab[j])
			{
				multitab[j] = schedule[i];
				pluggedCheck = true;
				break;
			}
		}
		if (pluggedCheck)
			continue;

		int far = -1;
		int index = 0;
		for (int j = 0; j < multitabCount; ++j)
		{
			int lastIndex = 0;
			for (int k = i + 1; k < scheduleCount; ++k)
			{
				if (schedule[k] == multitab[j])
					break;
				++lastIndex;
			}
			if (far < lastIndex)
			{
				index = j;
				far = lastIndex;
			}
		}
		++result;
		multitab[index] = schedule[i];
		
	}
	
	cout << result << endl;
}