[백준22234] 가희와 은행 (C++)

📌 문제

BOJ 바로가기

🗡 풀이

처음엔 우선순위 큐를 쓰지 않고 그냥 큐로만 풀었다. 그러니까 예제 출력은 맞게 나오는데 런타임 에러가 났다.. 다른 분들의 소스코드를 참고하니 우선순위 큐를 이용해서 푸셨길래 나도 그렇게 푸니까 맞았다. 수정 전 소스코드는 대충 이러했다.

🚩 수정 전 소스코드

	while (!q.empty()) {
		int front_p = q.front().first;
		int front_t = q.front().second;
		int temp_t = T;
		while ( front_t && temp_t) {
			cout << front_p << '\n';
			front_t--;
			temp_t--;
			time++;
			if (time == W)
				return 0;
			if (newbie[time].first != 0) {// 들어오는 고객이 있을 경우
				q.push({ newbie[time].first, newbie[time].second });
			}
		}
		q.pop();
		if (front_t != 0) // 고객이 다시 줄서는 경우
			q.push({ front_p, front_t });
	}

🥶 고객이 들어오는 시간과 고객 정보를 newbie 벡터에 저장했다. 그리고 매 시간마다 들어오는 고객이 있는지 체크해서 있다면 큐에 넣었다. 런타임에러(OutOfBounds)가 났는데 아직도 문제 원인을 잘 모르겠다.. ㅠㅠ

아무튼 정답을 찾은 로직은 다음과 같다.

📍 새로 들어올 예정인 손님 정보를 우선순위 큐에 넣는다. 일찍 들어오는 순서대로 자동 정렬된다.

📍 고객이 일을 처리하는 데 걸리는 시간 front_t와 제한시간 T를 동시에 줄여가며 어느 한 쪽이 0이 되는 순간 반복문을 종료한다. (또는 time이 W가 되는 순간 종료한다.)

📍 고객의 일처리가 끝났거나 제한시간이 다 됐다면 pq.top().first의 값이 time보다 작은 고객을 전부 push한다. (새로 들어온 손님)

📍 제한시간이 다 돼서 일처리가 끝나지 않았는데 쫓겨난 고객은 다시 큐에 push한다. 이때 front_t는 일이 끝나기 위해 필요한 남은 시간이다.

🚩 정답 소스코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
	queue<pair<int, int>> q;
	priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> pq;
	int N, T, W, M;
	cin >> N >> T >> W;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		q.push({ a, b });
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		pq.push({ c, {a, b} });
	}
	int time = 0;
	while (!q.empty()) {
		int front_p = q.front().first;
		int front_t = q.front().second;
		int temp_t = T;
		while ( front_t && temp_t) {
			cout << front_p << '\n';
			front_t--;
			temp_t--;
			time++;
			if (time == W)
				return 0;
		}
		q.pop();
		// 새로운 고객이 들어오는 경우
		while (!pq.empty() && time >= pq.top().first) {
			q.push(pq.top().second);
			pq.pop();
		}
		if (front_t != 0) // 고객이 다시 줄서는 경우
			q.push({ front_p, front_t });
	}
}