백준 1700(멀티탭 스케줄링)

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

1700번: 멀티탭 스케줄링

 

그리디 스터디중에 푸는 문제인데 내가 생각했던 그리디보다는 좀 그리디답지 않은 문제였다. 

 

정해진 갯수의 콘센트에 전자기기를 꽂아서 사용할 수 있는데, 전자기기의 사용순서가 있어서 콘센트에서 코드를 뽑는 횟수가 최소가 되게끔 만드는게 이 문제이다. 

 

엄청 단순하고 명확하다 

 

그냥 제일 늦게 사용하는거를 뽑아서 사용하면 되지 않을까 만약에 이미 꽂혀있는거면 그대로 꽂아서 사용하면 되고. 

 

그래서 단순하게 빨리 코드를 짜려고 노력을 했지만 계속 머릿속에서 둥둥 떠다니기만 하고 뭐를 먼저 짜야하는지 이 코드를 구현할때 예외가 뭔지 너무 헷갈려서 고생을 했다. 

 

한 두시간 정도 고생한 끝에야 머릿속에 있는걸 의사코드로 적어보자 했고, 

 

아래의 코드가 내가 생각한 방법이다. 

 

 

1. 모든 콘센트에 전자기기를 꽂아서 사용 (콘센트가 꽉 찰때까지 별 생각없이 꽂는다)

=> 이 때 우선순위를 정한다. 만약에 앞으로 사용 안 할 기기라면 절대 도달할 수 없는 우선순위인 INF(MAX)로 넣었다.

 

	for (int i = 1; i <= K; i++) {
		int a;
		cin >> a;
		elec[i] = a;
		if (num == N && whosturn[a] == MAX) {
			whosturn[a] = i;
		}
		if (num < N) {
			if (!on[a]) {
				num++;
				on[a] = true;
			}
			idx = i;
		}
	}

 

2. 다 꽂힌 상태에서 다음 사용기기가 안 꽂혀 있으면 

2-1. 꽂혀 있는 것 중에서 우선순위 중 가장 낮은 기기를 뺀다. (우선순위 => 초기 index) 기기마다 우선순위 배열값 결정

=> 우선순위 최신화 

그리고 ans + 1 해준다. 

 

plug = 빼는 전자기기 

if (!on[elec[i]]) {
			for (int j = 1; j <= K; j++) {
				if (on[j]) {
					if (max_n < whosturn[j]) {
						max_n = whosturn[j];
						plug = j;
					}
				}
			}

			if (plug != -1) {
				ans++; 
				on[plug] = false;
				on[elec[i]] = true;
				whosturn[elec[i]] = MAX;
				for (int j = i + 1; j <= K; j++) {
					if (elec[j] == elec[i]) {
						whosturn[elec[i]] = j;
						break;
					}
				}
			}
			plug = -1;
			max_n = 0;
		}

3. 이미 꽂혀 있던 전자기기여도 우선순위 최신화  

 

		else {
			for (int j = i + 1; j <= K; j++) {
				if (elec[j] == elec[i]) {
					whosturn[elec[i]] = j;
					break;
				}
				if (j == K)
					whosturn[elec[i]] = MAX;
			}
		}

2. 3.  마지막 전자기기까지 반복

 

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 105

int N, K, num, idx, plug=-1, ans, max_n;
int elec[MAX];
int whosturn[MAX];
bool on[MAX];

int main() {
	cin >> N >> K;
	for (int i = 1; i <= K; i++) {
		whosturn[i] = MAX;
	}
	for (int i = 1; i <= K; i++) {
		int a;
		cin >> a;
		elec[i] = a;
		if (num == N && whosturn[a] == MAX) {
			whosturn[a] = i;
		}
		if (num < N) {
			if (!on[a]) {
				num++;
				on[a] = true;
			}
			idx = i;
		}
	}

	for (int i = idx + 1; i <= K; i++) {
		if (!on[elec[i]]) {
			for (int j = 1; j <= K; j++) {
				if (on[j]) {
					if (max_n < whosturn[j]) {
						max_n = whosturn[j];
						plug = j;
					}
				}
			}

			if (plug != -1) {
				ans++; 
				on[plug] = false;
				on[elec[i]] = true;
				whosturn[elec[i]] = MAX;
				for (int j = i + 1; j <= K; j++) {
					if (elec[j] == elec[i]) {
						whosturn[elec[i]] = j;
						break;
					}
				}
			}
			plug = -1;
			max_n = 0;
		}
		else {
			for (int j = i + 1; j <= K; j++) {
				if (elec[j] == elec[i]) {
					whosturn[elec[i]] = j;
					break;
				}
				if (j == K)
					whosturn[elec[i]] = MAX;
			}
		}
	}
	cout << ans << "\n";

}

 

 

생각을 구체화하자