문제
주택난을 해결하기 위해서 직선 도로 하나를 따라 여러 아파트 단지들을 지었다. 또, 이 아파트 단지 주민을 위해 도로 위 한 지점에 학교 하나를 신설하였다. 아파트 단지들이 서로 멀리 떨어져 있기 때문에 반드시 통학버스를 이용해서만 다닐 수 있고, 통학버스는 한 대이다.
각각의 아파트 단지와 학교의 위치는 도로 위의 좌표로 주어지며, 또 각 아파트 단지마다 여기에 사는 학생들의 수도 주어진다. 통학버스는 아침에 학교를 출발하여 각 아파트 단지에 있는 학생들을 태우고 학교로 다시 돌아온다. 이 통학버스는 정원을 초과하여 학생을 태울 수 없고, 모든 학생을 등교시킬 때까지 이 과정을 반복한다.
위 규칙을 따라서 모든 학생들을 학교에 등교시키는 예를 보자. 아파트 단지 A, B, C가 각각 좌표 0, 2, 5에 있고 이 단지에 사는 학생은 각각 1, 2, 1명이라고 하자. 두 지점 간의 거리는 두 지점 좌표의 차이로 정의된다. 최대 4명이 탈 수 있는 통학버스가 좌표 4에 있는 학교에서 출발해서 모든 학생들을 등교시킬 때, 버스는 먼저 단지 B를 들러 2명을 태우고, 단지 A를 들러서 1명을 태우고 다시 학교로 돌아온다면 이동 거리는 2 + 2 + 4 = 8이다. 다시 학교에서 아파트 단지 C로 이동하여 1명을 태우고 돌아오면 이동 거리는 1 + 1 = 2가 되고, 총 이동거리는 8 + 2 = 10이 된다.
학교의 위치, 각각의 아파트 단지의 위치와 학생 수, 통학버스의 정원이 주어졌을 때, 모든 학생을 등교시키는데 필요한 통학버스의 총 이동 거리의 최솟값을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원이다. 세 번째 정수 S는 학교의 위치를 나타낸다. 둘째 줄부터 N+1번째 줄에는 각 아파트 단지의 위치를 나타내는 정수와 이 단지에 사는 학생 수를 나타내는 정수가 빈칸을 사이에 두고 주어진다. 학교와 아파트 단지의 좌표는 0 이상 100,000 이하이며, 이 좌표들은 모두 서로 다르다. 각 아파트 단지의 학생 수는 1 이상 2,000 이하이다.
출력
첫째 줄에 주어진 입력에서 통학버스의 최소 이동 거리를 출력한다. 최소 이동 거리가 1,000,000,000을 초과하는 경우는 없다.
접근 방법
-
학교로부터 떨어진 거리 순으로 탐색해야된다는 느낌이 강하게 옵니다..! 그렇습니다 그리디 알고리즘입니다.
-
학교를 기준으로 왼쪽, 오른쪽을 구분 한 뒤 우선순위 큐에 저장합니다. 이때, 거리가 먼 순서대로 우선순위를 부여해주어야 합니다.
-
우선순위 큐에서 하나씩 poll() 해가며 버스의 정원 만큼 학생들을 태우는 방식으로 왕복합니다.
⚠️주의⚠️
거리가 먼 단지를 우선으로 탐색해야 합니다. 가까운 곳을 우선으로 잡게 되면 다음 단지를 가는 선택과 가지 않는 선택을 유추하기 어려워집니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class SchoolBus {
static int n, k, s; // 아파트 단지수, 통학버스의 정원, 학교의 위치
static class Location implements Comparable<Location>{
int locate;
int student;
public Location(int locate, int student) {
this.locate = locate;
this.student = student;
}
@Override
public int compareTo(Location o) {
return o.locate - this.locate;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
k = Integer.parseInt(input[1]);
s = Integer.parseInt(input[2]);
PriorityQueue<Location> leftSide = new PriorityQueue<>();
PriorityQueue<Location> rightSide = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
input = br.readLine().split(" ");
int dist = Integer.parseInt(input[0]);
int student = Integer.parseInt(input[1]);
if (dist < s) {
leftSide.offer(new Location(s - dist, student));
} else {
rightSide.offer(new Location(dist - s, student));
}
}
int result = 0;
result += busMoveTime(leftSide); // 학교를 기준으로 왼쪽에 있는 단지들
result += busMoveTime(rightSide); //학교를 기준으로 오른쪽에 있는 단지들
System.out.println(result);
}
// 우선순위 큐의 값은 학교에서 가장 먼 순서대로 높은 우선순위를 가집니다
// 가장 멀리 있는 단지의 학생들을 태워오며 버스에 빈자리가 있을 경우 다음으로 먼 단지를 탐색해서 버스에 태웁니다
// 모든 단지의 학생을 태우는 동안의 왕복 거리를 move에 저장해서 반환합니다
public static int busMoveTime(PriorityQueue<Location> locations) {
int move = 0;
while (!locations.isEmpty()) {
Location now = locations.poll();
int cnt = now.student / k; // 해당 단지를 왕복하는 횟수
if (now.student % k > 0) {
cnt++;
}
int rem = k * cnt - now.student; // 데려가고 남은 학생 수
while (!locations.isEmpty()) {
Location next = locations.poll();
if (next.student <= rem) {
rem -= next.student;
} else {
next.student -= rem;
locations.offer(next);
break;
}
}
move += (2 * cnt * now.locate);
}
return move;
}
}결과
