[SWEA] #2477 _ 차량 정비소

[차량 정비소] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

tk는 도착한 시간을 저장하는 큐로 손님의 수만큼 값을 저장한다.

v_a, v_b는 a창구와 b창구 이용하는 손님을 가지는 벡터이다.

 

checkPossible() 함수는 사용 가능한 창구 번호를 반환해준다.

tk가 현재 시간인 time보다 작거나 같아지면, 손님이 도착한 것이기 때문에 wait 큐에 넣어준다.

(이때, wait은 우선순위 큐를 이용하여 손님의 우선 순위대로 pop 되도록 구현하였다.)

 

시간이 흐르다 사용 가능한 b창구가 생기면 wait 큐에서 반환된 손님이 창구를 이용한다.

getSumNumber() 함수를 이용하여, 주어진 창구에서 이용한 손님의 합을 구하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 10

using namespace std;

typedef struct person {
	int number = 0;
	int a_num = 0;
	int b_num = 0;
	int time = -1;
}Person;

struct cmp {
	bool operator()(Person a, Person b) {
		if (a.time == b.time) {
			return a.a_num > b.a_num;
		}
		else return a.time > b.time;
	}
};

int N, M, K, A, B, num = 1;
int a[MAX], b[MAX], chk_a[MAX], chk_b[MAX];
vector<int> tmp_tk;
queue<int> tk;
queue<Person> person_q;

void init();
void solve();
int checkPossible(int a_b);
int getSumNumber();
int main() {
	int T, tmp, result;

	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d %d %d %d %d", &N, &M, &K, &A, &B);
		for (int j = 1; j <= N; j++) scanf("%d", &a[j]);
		for (int j = 1; j <= M; j++) scanf("%d", &b[j]);
		for (int j = 0; j < K; j++) {
			scanf("%d", &tmp);
			tk.push(tmp);
			tmp_tk.push_back(tmp);
		}

		solve();
		init();

		result = getSumNumber();
		if (result == 0) result = -1;
		printf("#%d %d\n", i, result);
	}
	return 0;
}

void init() {
	num = 1;
	for (int i = 1; i <= N; i++) chk_a[i] = 0;
	for (int i = 1; i <= M; i++) chk_b[i] = 0;
	tmp_tk.clear();
}

void solve() {
	vector<Person> v_a, v_b;
	priority_queue<Person, vector<Person>, cmp> wait;
	Person tmp;
	int check, time = 0;

	while (!tk.empty()) {
		for (int i = 0; i < v_b.size(); i++) {
			v_b[i].time--;
			if (v_b[i].time <= 0) {
				chk_b[v_b[i].b_num] = 0;
				tk.pop();
				person_q.push(v_b[i]);
				v_b.erase(v_b.begin() + i);
				i--;
			}
		}

		for (int i = 0; i < v_a.size(); i++) {
			v_a[i].time--;
			if (v_a[i].time <= 0) {
				chk_a[v_a[i].a_num] = 0;
				v_a[i].time = time;
				wait.push(v_a[i]);
				v_a.erase(v_a.begin() + i);
				i--;
			}
		}

		while (!wait.empty()) {
			check = checkPossible(0);
			if (check > 0) {
				tmp = wait.top();
				wait.pop();
				chk_b[check] = 1;
				tmp.b_num = check;
				tmp.time = b[check];
				v_b.push_back(tmp);
			}
			else break;
		}

		while (num <= K) {
			if (tmp_tk[num - 1] > time) break;
			check = checkPossible(1);
			if (check > 0) {
				chk_a[check] = 1;
				tmp.number = num++;
				tmp.a_num = check;
				tmp.time = a[check];
				v_a.push_back(tmp);
			}
			else break;
		}
		time++;
	}

}

int checkPossible(int a_b) {
	if (a_b == 1) {
		for (int i = 1; i <= N; i++) if (!chk_a[i]) return i;
	}
	else {
		for (int i = 1; i <= M; i++) if (!chk_b[i]) return i;
	}

	return 0;
}

int getSumNumber() {
	Person tmp;
	int result = 0;

	while (!person_q.empty()) {
		tmp = person_q.front();
		person_q.pop();

		if (tmp.a_num == A && tmp.b_num == B) result += tmp.number;
	}

	return result;
}