[백준] 멀티탭 스케쥴링 C++

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

 

그리디 문제이다.

본인은 첫트에 틀렸다.. (어렵더라..)

왜 틀렸냐면은 멀티탭이 꽉차 있는 상태, 아닌 상태, 사용중인지 아닌지를 판별하고 있었다.

 

멀티탭이 꽉차있지 않다면 그냥 꼽고 해당 제품 번호를 사용중으로 변경해주면된다.

근데 문제는 '멀티탭이 꽉차 있을 때' 이다.

이때 뭘 뽑아야 최적의 선택으로 이어질지 고민을 해야한다.

 

본인은 멀티탭이 꽉차 있을 때, 앞으로 사용횟수가 가장 작은 것을 찾아 해당 제품을 뽑으면 최적이 아닐까? 생각했었고 이대로 코드를 짜서 O(N^2)로 풀었는데 틀렸다.

 

최적의 경우는 '앞으로 사용할 번째 수가 가장 뒤에 있거나가장 나중에 사용) 사용하지 않을 제품을 뽑는 것'이 최적이다.

예시로 ' 1 2 3 2 4 1 3 1' 의 경우 멀티탭 개수가 2개라 하자. 

앞으로 사용횟수가 가장 작은 것을 기준으로 뽑다 보면 교체 횟수가 4번이 나오고

위의 최적의 경우(앞으로 사용할 번째가 가장 뒤에 있거나 사용하지 않을 제품을 뽑는)로 뽑으면 3번이 나온다.

 

앞으로 사용횟수가 가장 작은 것을 뽑는다고 하자. 근데 만약 자주 사용하는 제품을 뽑아 버리면 다시 다른 제품을 뺏다가 꼽아야 하는 상황이 발생할 수 있다.

그래서 가장 나중에 사용하거나, 사용하지 않는 제품을 뽑아야지, 다른 제품을 꽂을 수 있는 시간을 최대한 벌 수 있다.

 

이해가 잘 안간다면  ' 1 2 3 2 4 1 3 1' 를 예시로 공책에다가 적어보도록 하자.

 

코드

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
#include <climits>
#include <limits>
using namespace std;

#define endl "\n"
#define X first
#define Y second
#define R first
#define C second
using ll = long long;

int order[104];
bool use[104];

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

	int n, k; cin >> n >> k;
	for (int i = 1; i <= k; ++i) cin >> order[i];
	int ret = 0;	// 결과
	int cnt = 0;	// 사용중인 횟수
	for (int i = 1; i <= k; ++i)
	{
		int cur = order[i];			
		if (use[cur]) continue;		// 이미 사용중이라면 넘어간다.

		// 멀티탭에 자리가 있으면 그냥 꼽는다.
		if (cnt < n)
		{
			use[cur] = true;
			cnt++;
		}
		else
		{
			// 멀티탭에 꽃혀 있는 전기용품 중 order에서 앞으로 가장 빨리 나올 위치를 이름과 함께 저장한다.

			// 아래 코드는 가장 나중에 사용되거나 사용하지 않는 제품을 찾는 로직이다.
			vector<pair<int, int>> idx;
			for (int x = 1; x <= k; ++x)
			{
				if (!use[x]) continue;	// 사용중인게 아니라면 건너뛴다.
				bool vis = false;
				for (int y = i + 1; y <= k; ++y) // i + 1번부터 탐색한단.
				{
					if (order[y] == x) 
					{
						idx.push_back({ y, x }); // 사용순서, 제품 번호 순으로 저장.
						vis = true;
						break;
					}
				}
				if (!vis) idx.push_back({ k + 1, x });
			}

			// 내림 차순으로 정렬, 사용순서가 가장 큰게 앞으로 온다.
			// - 즉 가장 마지막에 사용하는 순서, 제품 번호 순으로 0번에 온다.
			sort(idx.begin(), idx.end(), greater<pair<int, int>>());
			int target = idx[0].Y;
			use[target] = false;
			++ret;
			use[cur] = true;
		}
	}
	cout << ret;
}