[C++] BOJ(백준) 1700 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

 

그리디 문제다.

 

멀티탭에 플러그를 꽂되, 플러그를 최대한 적게 빼는 횟수를 구하는 문제다.

입력된 멀티댑 사용 순서는 유지 해야 하므로 앞에서부터 접근했다.

 

1. 해당 플러그가 이미 꽂혀 있는지 확인

2. 플러그에 빈 자리가 있다면 꽂기

3. 빈 자리가 없다면 현재 꽂힌 플러그 중 가장 나중에 사용되는 플러그를 뽑는다.

 

3번을 처리하는 구현이 살짝 까다로웠지만 알고리즘 자체를 생각해내는데 어렵진 않았다.

 

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

int n, m, res;
int arr[100];
vector<int> v;

bool already(int i) {
	for (int j = 0; j < v.size(); j++)
		if (v[j] == arr[i]) return true;
	return false;
}

int main() {
	// 입출력 속도 향상을 위함
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> arr[i];

	for (int i = 0; i < m; i++) {
		if (already(i)) continue;
		if (v.size() < n) {
			v.push_back(arr[i]);
			continue;
		}

		int ma = 0, index = -1;
		for (int j = 0; j < n; j++) {
			bool tmp = true;
			for (int k = i + 1; k < m; k++) {
				if (v[j] == arr[k]) {
					if (index < k) {
						ma = j;
						index = k;
					}
					tmp = false;
					break;
				}
			}
			if (tmp) {
				ma = j;
				break;
			}
		}
		v.erase(v.begin() + ma);
		v.push_back(arr[i]);
		res++;
	}
	cout << res;
}