백준 19640 화장실의 규칙

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

19640번: 화장실의 규칙

문제

데카는 회사의 화장실을 이용하려고 했다. 하지만 수도 시설 고장으로 회사 내의 모든 화장실 사용이 금지됐고, 사원들은 단 하나의 임시 화장실을 이용해야 했다. 

임시 화장실의 앞에 데카를 포함한 N명의 사원이 대기하고 있다. 데카는 N명의 줄에서 K + 1번째로 줄을 섰다. 즉, 데카보다 먼저 도착한 사람이 K명이 있다. 줄이 길어지자 사장은 M개의 줄로 나눠서 대기하라 하였다.

N명의 사원은 순서대로 M개의 줄로 나눠 섰다. 기존 줄의 1번째 사원은 1번째 줄에, 2번째 사원은 2번째 줄에, ... M번째 사원은 M번째 줄에, 그리고 M + 1번째 사원은 1번째 줄의 뒤에 서는 방식이다. 

M개의 줄로 나눠 선 것을 본 사장은 매우 흡족해하며 자리를 떠났다.

M개의 줄의 사원들은 암묵적으로 다음의 규칙에 따라 화장실을 이용하기로 하였다.

• 선두란, 어떤 줄에서 가장 먼저 와서, 가장 앞에 선 사람을 말한다.
• M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 화장실을 이용한다.
• M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상인 경우, 해당 선두들 중 화장실이 급한 정도 Hi가 가장 높은 선두가 화장실을 이용한다.
• M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상이며, 해당 선두들의 화장실이 급한 정도 Hi도 모두 같다면, 해당 선두 중 줄의 번호가 가장 낮은 줄에 선 선두가 화장실을 이용한다.

과연 몇 명의 사원이 화장실을 이용하고 나서야 데카의 차례가 올까? 매우 초조해지기 시작한 데카를 대신해 계산해주자.

입력

첫 번째 줄에는 임시 화장실에 대기하고 있는 사원의 수 N (1 ≤ N ≤ 105), 사장이 지시한 새로운 줄의 수 M (2 ≤ M ≤ 105), 데카가 화장실에 도착했을 때 자신의 앞에 서 있던 사원의 수 K (0 ≤ K ≤ N − 1)가 빈칸을 사이에 두고 주어진다.

두 번째 줄부터 각 N개의 줄에 임시 화장실에 i번째로 줄을 섰던 사원의 근무 일수 Di (0 ≤ Di ≤ 36,500), 화장실이 급한 정도를 나타내는 정수 Hi (0 ≤ Hi ≤ 108)가 가장 먼저 도착한 사원부터 빈칸을 사이에 두고 주어진다.

출력

데카가 화장실을 이용하기까지 몇 명의 사원이 화장실을 이용할 것인지 출력한다.

예제 입력 1 

6 3 2

3000 100

1500 200

1000 500

1500 100

1500 100

1500 100

예제 출력 1 

4

---

[풀이 과정]

<구조체 info>

- idx : 몇 번째 줄인지

- d : 근무 일수

- h : 화장실이 급한 정도

- deca : 데카이면 1, 아니면 0

 

1. n명의 정보를 입력 받는다. 이때 i가 k이면 데카이므로 deca변수에 1을 넣는다.

 

2. m번 반복하면서 각 줄에서 첫번째 사람을 first_person 우선순위 큐에 넣는다.

- compare 구조체 : 일반적인 sort함수와는 반대로 생각해야한다. 

                          info a, info b가 주어질 때

                          두번째로 들어온 b가 기존의 a보다 우선순위가 높으면 true, 낮으면 false

 

3. 데카가 나올 때가지 반복한다.

- 우선순위대로 정렬된 first_person의 첫번째 사람의 인덱스를 저장 후 pop한다.

- 먼저 나갈 사람이 데카인지 확인한다.

- 나간 사람의 줄에 사람이 있으면 새로운 첫번째 사람을 first_person에 넣는다.

- cnt를 1 증가시킨다.

 

4. cnt를 출력한다.

 

처음 두번은 시간초과가 났다. 

1. 매번 m번 돌리며 새로운 first_person을 구함.

2. first_person은 지금처럼 고쳤는데 deque와 sort를 사용해서 먼저 나갈 사람을 구함.

 

sort의 시간복잡도는 NlogN이고 priority_queue는 시간복잡도가 logN이다.

사용법 좀 더 익혀서 많이 사용해야겠다.     

---

[소스 코드]

#include <cstdio>
#include <deque>
#include <queue>
using namespace std;
const int MAX = 100005;

struct info {
	int idx, d, h, deca;
};

struct compare {
	bool operator()(info a, info b) {
		if (a.d > b.d) return false;
		else if (a.d == b.d) {
			if (a.h > b.h) return false;
			else if (a.h == b.h) {
				if (a.idx < b.idx) return false;
			}
		}
		return true;
	}
};

int n, m, k;
deque <info> dq[MAX];
priority_queue <info, vector<info>, compare> first_person;

int main() {
	scanf("%d %d %d", &n, &m, &k);

	int idx = 0;
	for (int i = 0; i < n; i++) {
		int d, h;
		scanf("%d %d", &d, &h);
		if (i == k) dq[idx].push_back({ idx, d, h, 1 });
		else dq[idx].push_back({ idx, d, h, 0 });
		idx++;
		if (idx == m) idx = 0;
	}

	for (int i = 0; i < m; i++) {
		if (dq[i].empty()) continue;
		first_person.push(dq[i][0]);
	}
	
	int cnt = 0;
	while (1) {
		int idx = first_person.top().idx;
		first_person.pop();

		if (dq[idx][0].deca == 1) break;
		dq[idx].pop_front();

		if (!dq[idx].empty()) first_person.push(dq[idx][0]);
		cnt++;
	}

	printf("%d\n", cnt);
	return 0;
}