[BOJ 2513 // C++] 통학버스

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

 

이번에 볼 문제는 백준 2513번 문제인 통학버스이다.
문제는 아래 링크를 확인하자.

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

2513번: 통학버스

학교를 기준으로 왼쪽에 있는 아파트와 오른쪽에 있는 아파트들은 서로 다른 별개의 문제로 취급할 수 있다는 점을 발견하자. 그 이유는 왼쪽의 아파트와 오른쪽의 아파트를 모두 들리는 경로는 그 사이에 있는 학교를 경유할 수밖에 없기 때문이다.

 

가장 멀리 있는 아파트를 최소한으로 들리는게 항상 이득이므로, greedy하게 접근하여 가장 먼 아파트의 학생들서부터 차례로 등교시키자.

 

이 때, 버스의 정원이 매우 작은 숫자이고 아파트에 사는 학생 수가 매우 큰 숫자라면 버스의 왕복횟수가 매우 많아질 수 있으므로, 버스의 왕복을 그대로 시뮬레이션하면 문제를 해결할 수 없다. 적절한 수식으로 계산해주자.

 

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

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

priority_queue<pair<int, int>> pqL, pqR;

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

	ll ans = 0;
	int N, K, S; cin >> N >> K >> S;
	while (N--) {
		int x, w; cin >> x >> w;
		if (x < S) pqL.push(make_pair(S - x, w));
		else if (x > S) pqR.push(make_pair(x - S, w));
	}

	int bus = 0;
	while (!pqL.empty()) {
		auto current = pqL.top(); pqL.pop();
		if (bus + current.second < K) {
			if (bus == 0) ans += current.first * 2;
			bus += current.second;
		}
		else {
			if (bus) {
				current.second -= K - bus;
				bus = 0;
			}
			ans += current.first * 2 * (current.second / K);
			current.second %= K;
			if (current.second) {
				bus = current.second;
				ans += current.first * 2;
			}
		}
	}

	bus = 0;
	while (!pqR.empty()) {
		auto current = pqR.top(); pqR.pop();
		if (bus + current.second < K) {
			if (bus == 0) ans += current.first * 2;
			bus += current.second;
		}
		else {
			if (bus) {
				current.second -= K - bus;
				bus = 0;
			}
			ans += current.first * 2 * (current.second / K);
			current.second %= K;
			if (current.second) {
				bus = current.second;
				ans += current.first * 2;
			}
		}
	}

	cout << ans;
}