백준 - 1700번 멀티탭 스케줄링

문제

플러그를 최소로 빼면서 멀티탭을 쓰고 싶음
몇 번 빼야할까?

생각

컴공 운체 배운 피플이라면 쉽게 생각할 법한 방법

빈 플러그가 없을 때 새로운 전자기기를 꽂을 플러그를 마련하기 위해
현재 플러그에 꽂힌 전자기기들 중 제일 나중에 쓸 전자기기를 빼주자~!~!!

누가 제일 나중에 쓰이냐

뭐 어려운 건 없고 n개 플러그가 다 꽂힌 경우엔
뒤에 나오는 정보들 보면서 플러그에 있는 애들 n-1개 발견하면
안 발견한 애가 제일 늦게 쓰이거나 안 쓰이는 경우니까 걔를 빼준다

주의해야 할 점

위와 같이 구현하면 멀티탭 구멍의 개수가 1일 때 잘 안 돌아간다
k-1개를 보기때문에~~! 1개일 때도 잘 돌아가게 해주자

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <functional>

using namespace std;

int info[105];
int plug[105];
int check[105];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, k, tempn = 0, result = 0;

	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> info[i];
	}

	for (int i = 0; i < k; i++) {
		if (check[info[i]] != 1) { //플러그에 이 전자 기기 안 꽂힘
			if (tempn < n) { //비어있는 곳이 있음
				plug[tempn++] = info[i];
				check[info[i]] = 1;
			}
			else { //플러그를 빼야해
				int count = 0;
				for (int j = i + 1; j < k; j++) {
					if (count == n - 1) { //플러그가 1개일 수 있으니까 이거 먼저 해줘야해
						break;
					}
					if (check[info[j]] == 1) { //꽂힌 애들 기입하자
						check[info[j]] = j;
						count++;
					}
				}
				bool flag = true;
				//다하고 나면 그 뒤에 나오는 숫자 혹은 하나도 안나와서 1이겠지
				for (int j = 0; j < n; j++) {
					if (check[plug[j]] == 1) { //빼내 새로운 애 넣어
						if (flag) {
							result++;
							check[plug[j]] = 0;
							plug[j] = info[i];
							check[info[i]] = 1;
							flag = false;
						}
					}
					else {
						check[plug[j]] = 1;
					}
				}
			}
		}
	}

	cout << result;

	return 0;
}