BOJ 1700 멀티탭 스케줄링

BOJ 1700 멀티탭 스케줄링

문제링크 : https://www.acmicpc.net/problem/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";
}