BOJ 1700 멀티탭 스케줄링

문제 링크 : https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

요약

멀티탭의 구멍 개수와 전기용품의 사용 횟수 K가 주어지고 K개만큼의 전자용품을 사용한 순서대로 전자용품 이름(숫자)이 주어지는데 가장 플러그를 덜 빼고 모든 전기용품을 사용할 수 있는 방법을 구하는 문제이다.

풀이

어떻게 풀어야 할지는 빠르게 떠올랐다. 하지만 구현이 생각보다 까다로웠던 문제..

1. 빈 멀티탭이 있다면 비어있는 공간에 우선적으로 끼워준다.
2. 현재 사용해야 하는 전기용품이 이미 꽂혀있다면 그냥 넘어간다.
3. 빈멀티탭이 없을 때 새로운 전기용품을 사용해야 하면 꼽혀있는 전기용품 중 가장 나중에 사용되는 코드를 뽑고 꼽는다.

이 과정을 구현해주면 되는 문제이다.

코드

#include<iostream>
using namespace std;
int n, k, arr[101], check[101], cnt[101],big, ans;
int main() {
	int count = 0;
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> arr[i];
		cnt[arr[i]]++;
	}
	for (int i = 0; i < k; i++) {
		if (check[arr[i]] == 1) {
			cnt[arr[i]]--;
		}
		else {
			if (count < n) {
				check[arr[i]] = 1;
				cnt[arr[i]]--;
				count++;
			}
			else {
				int last[101] = { 0,};
				int now = 0;
                big = -1e9;
				for (int j = 0; j < i; j++) {
					if (check[arr[j]]) {
						if (!cnt[arr[j]]) now = arr[j];
					}
				}
				if (now == 0) {
					for (int j = i + 1; j < k; j++) {
						if (check[arr[j]] && last[arr[j]] == 0) last[arr[j]] = j;
					}
					for (int j = 0; j < k; j++) {
						if (last[arr[j]]) {
							if (big < last[arr[j]]) {
								big = last[arr[j]];
							}
						}
					}
					now = arr[big];
				}
				check[now] = 0;
				ans++;
				check[arr[i]] = 1;
				cnt[arr[i]]--;
			}

		}
	}
	cout << ans << "\n";
}