BOJ 2513 통학버스

사용한 알고리즘

그리디 알고리즘

알고리즘 설명

시작점(학교)로 부터 좌측과 우측의 학생으로 나눈다.
먼저 좌측의 학생을 학교로 데려오는 경우를 생각하자.
버스는 항상 최대한 많은 학생을 버스에 태워오는 것이 좋다.
이 중 학교에서 가장 멀리 있는 학생을 태우고 돌아오면서 그 다음으로 멀리 있는 학생을 태울 수 있는 만큼 태운다.
위 알고리즘이 가능한 이유는 가까이 있는 학생을 먼저 태우고 온다고 해도 언젠가는 가장 멀리 있는 학생의 거리를 들여 가야 한다는 것이 분명하다.

풀이

// baekjoon 2513 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=30001;
const int MAX_K=2001;

int N, K, S, x, y;
int lpos, rpos;
pair<int, int> left[MAX_N], right[MAX_N];

int main() {
	scanf("%d%d%d", &N, &K, &S);
// 좌측학생과 우측 학생을 구분하여 태운다.
	for (int i=0; i<N; i++) {
		scanf("%d%d", &x, &y);
		if (S < x) right[rpos++] = make_pair(x-S, y);
		else left[lpos++] = make_pair(S-x, y);
	}
	sort(left, left+lpos);
	sort(right, right+rpos);

	int start = lpos-1;

// 먼저 좌측 학생부터 태우기 시작한다.
	int d = 0;
	while (start >= 0) {
// 버스에 태울수 있는 학생 수
		int cap = K;
// 가장 멀리 갔다가 다시 돌아오는 거리를 더한다.
		d += left[start].first*2;
		while (start >= 0 && cap) {
// 태울 수 있는 학생수 ride
			int ride = min(left[start].second, cap);
// 태운 학생 수 만큼 버스 용량 감소
			cap -= ride;
// 태운만큼 학생수 줄이기
			left[start].second -= ride;
// start위치에 학생을 모두 태웠다면 다음 지점으로 이동
			if (!left[start].second) start--;
		}
	}

// 좌측 학생 태우는 형태와 같은 형태의 알고리즘 반복
	start = rpos - 1;
	while (start >= 0) {
		int cap = K;
		d += right[start].first*2;
		while (start >= 0 && cap) {
			int ride = min(right[start].second, cap);
			cap -= ride;
			right[start].second -= ride;
			if (!right[start].second) start--;
		}
	}
	printf("%d\n", d);
	return 0;
}