문제

문제 링크

해설

• 구현도 어렵지만, 구현하기 전에 문제를 풀기위한 아이디어를 떠올리는 것도 어려운 문제입니다.
• 플러그를 빼는 횟수를 최소화하기 위해서는, 현재 꽂혀있는 플러그들 중 가장 먼 미래에 사용하거나, 아예 사용할 계획이 없는 플러그를 뽑는것이 가장 좋습니다. 이 아이디어가 핵심입니다.
  • <예제 입력 1>에서, {2, 3, 2, 3, 1, 2, 7}을 보면,
  • 우선 멀티탭 구멍의 개수가 2개이므로, 첫 2개는 그냥 끼웁니다.
  • 다음으로, 2와 3은 멀티탭에 꼽혀있으므로 생략합니다.
  • 다음으로, 1은 멀티탭에 없기 때문에 현재 꼽혀있는 2, 3 중 하나를 빼야 합니다. 이제 무엇을 빼야 할지 결정해야 합니다.
    • 미래를 봅시다. 2는 사용할 예정이군요. 3은 아닙니다.
    • 그러므로 3을 뽑는 것이 최선입니다.
• 이런 과정을 거치면 최소 멀티탭 교체 횟수를 구할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, K, answer, arr[101];
bool used[101];
vector<int> plug;

pair<int, int> findTarget(int start) {
	int retIdx = 0, retVar = 0;
	for (const int& num : plug) {
		int tempIdx = 1e9;
		// 각 원소마다 start~K 사이에서 언제 등장하는지 구합니다.
		for (int i = start; i < K; ++i)
			if (num == arr[i]) { tempIdx = i; break; }
		if (retIdx < tempIdx) {
			retIdx = tempIdx;
			retVar = num;
		}
	}
	return {retIdx, retVar};
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N >> K;
	plug.reserve(N);
	for (int i = 0; i < K; ++i) cin >> arr[i];
	
	for (int i = 0; i < K; ++i) {
		if (used[arr[i]]) continue;
		if (plug.size() == N) {
			int targetIdx, targetVar;
			tie(targetIdx, targetVar) = findTarget(i + 1);
			plug.erase(find(begin(plug), end(plug), targetVar));
			used[targetVar] = false;
			answer++;
		}
		plug.push_back(arr[i]);
		used[arr[i]] = true;
	}
	cout << answer;
}

소스코드 링크

결과