[백준] 1700번 멀티탭 스케줄링

1700번: 멀티탭 스케줄링

제품 사용 순서대로 돌면서 세 가지 경우를 확인해주고

그 경우에 따라 처리해주면 된다.

 

1. 현재 제품이 멀티탭에 꽂혀있을 경우

-> 그냥 넘어간다.

 

2. 멀티탭이 다 안 채워져 있을 경우

-> 현재 제품의을 저장한다.

 

3. 플러그를 뽑아야하는 경우

-> 남은 순서동안 멀티탭에 꽂혀있는 제품을 쓰지 않는다면

그 제품의 플러그를 뽑는다.

 

-> 남은 순서동안 멀티탭에 꽂혀있는 제품이 모두 쓰인다면

가장 마지막으로 쓰이는 제품의 플러그를 뽑는다.

 

이대로 구현해주면 끝

#include <iostream>
#include <vector>
using namespace std;
vector <int> v;
int main() {
	int N, K, skip = 0, cnt = 0;
	cin >> N >> K;
	int arr[101];
	for (int k = 0; k < K; k++) cin >> arr[k];
	
	for (int i = 0; i < K; i++) {
		skip = 0;
		for (int j = 0; j < v.size(); j++) {
			if (arr[i] == v[j]) { //멀티탭에 꽂혀있는 제품일 경우
				skip = 1;
				break;
			}
		}
		if (!skip) {
			if (v.size() < N) v.push_back(arr[i]); //멀티탭을 다 안 채웠을 경우
			else { //플러그를 빼야하는 경우
				cnt++;
				int Max = 0, idx = 0, exit = 0;
				for (int k = 0; k < N; k++) {
					for (int j = i + 1; j < K; j++) {
						if (v[k] == arr[j]) {
							if (j > Max) { //가장 마지막에 쓰일 플러그를 저장한다
								Max = j;
								idx = k;
							}
							break;
						}
						else if (j == K - 1) { //쓰이지 않을 플러그가 있으면 그걸 뽑는다
							idx = k;
							exit = 1;
						}
					}
					if (exit) break;
				}
				v[idx] = arr[i];
			}
		}
	}
	cout << cnt;
	return 0;
}