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

[문제 링크]

1700번: 멀티탭 스케줄링

---

멀티탭에 빈 구멍이 없고, 꽂혀있는 전기용품 중에 이후에 사용하지 않는 전기용품이 존재하지 않을 경우, 이후에 쓰게 될 빈도수가 가장 적은 전기용품을 먼저 뽑는 방법이 최적해를 보장한다고 생각하고 풀었으나 잘못된 접근이여서 고생했던 문제였다.

 

빈도수가 가장 적은 전기용품을 뽑는 것이 아닌, 가장 나중에 사용하게 되는 전기용품을 뽑아야 항상 최적해를 보장한다.

 

따라서, 멀티탭에 빈 구멍이 있거나 이미 꽂혀있는 전기용품이라면 플러그를 뺄 필요 없이 넘어가고, 두가지 경우에 해당하지 않는다면 이후에 사용할 일이 없는 전기용품이 있는지 확인한 다음 있다면 그 전기용품을 뽑도록 하고, 없다면 가장 나중에 사용되는 전기용품을 찾아 그 전기용품을 뽑도록 구현하면 된다.

---

#include <iostream>
using namespace std;

int arrCnt[101], arr[101];
bool check[101];

int Greedy(int N, int K)
{
	int empty = N, cnt = 0;

	for (int i = 1; i <= K; i++)
	{
		if (!check[arr[i]])
		{
			if (empty == 0)
			{
				int pick;

				bool ck = true;
				for (int j = 1; j <= K; j++)
					if (check[j] && arrCnt[j] == 0)
					{
						ck = false;
						pick = j;
						break;
					}

				if (ck)
				{
					int idx[100], temp = 0;

					for (int j = i + 1; j <= K; j++)
					{
						if (check[arr[j]])
						{
							bool ck = true;
							for (int i = 0; i < temp; i++)
							{
								if (arr[j] == idx[i])
								{
									ck = false;
									break;
								}
							}

							if (ck)
							{
								idx[temp] = arr[j];
								temp++;
							}
						}

						if (temp == N)
						{
							pick = arr[j];
							break;
						}
					}
				}

				cnt++;
				check[arr[i]] = true;
				check[pick] = false;
			}
			else
			{
				check[arr[i]] = true;
				empty--;
			}
		}

		arrCnt[arr[i]]--;
	}

	return cnt;
}

int main(void)
{
	int N, K;
	cin >> N >> K;

	for (int i = 1; i <= K; i++)
	{
		cin >> arr[i];
		arrCnt[arr[i]]++;
	}

	cout << Greedy(N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 122 day