취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15804번 문제인 저거 못 타면 지각이야!!이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 버스정류장은 큐의 형태로 모델링이 가능하다.

문제 조건에서 주어진 순서를 이용해 각 버스가 들어올 때마다 (1) 나갈 수 있는 버스를 모두 내보내고, (2) 해당 버스가 들어올 빈 자리가 있으면 들여보내고 (3) 자리가 없다면 모든 버스를 내보낼 때까지 기다린 뒤 해당 버스를 정류장에 집어넣는 시뮬레이션을 돌려 문제를 해결하자.

위 시뮬레이션을 돌릴 때, 새로 들어오는 버스의 도착시간은 항상 이전에 들어오는 버스의 도착시간 이상이 되어야 한다는 점을 확인하자.

아래는 제출한 소스코드이다.

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

struct bus {
	int arrive;
	int depart;
	int idx;
	bus(int arrive, int depart, int idx) {
		this->arrive = arrive, this->depart = depart, this->idx = idx;
	}
};

int N, M;
deque<bus> dq;

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

	cin >> N >> M;
	while (M--) {
		int arrive, depart; cin >> arrive >> depart;
		while (!dq.empty()) {
			if (dq.front().depart <= arrive) dq.pop_front();
			else break;
		}

		if (dq.empty()) dq.push_back(bus(arrive, arrive + depart, 1));
		else if (dq.back().idx == N) {
			while (!dq.empty()) {
				arrive = max(arrive, dq.front().depart);
				dq.pop_front();
			}
			dq.push_back(bus(arrive, arrive + depart, 1));
		}
		else {
			arrive = max(arrive, dq.back().arrive);
			dq.push_back(bus(arrive, arrive + depart, dq.back().idx + 1));
		}
	}
	cout << dq.back().idx;
}