[백준] 2513번. 통학버스(JAVA)

문제

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

---

풀이(15분)

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 아파트 단지 수
		int K = Integer.parseInt(st.nextToken()); // 통학버스 정원
		int S = Integer.parseInt(st.nextToken()); // 학교 위치

		PriorityQueue<Node> leftQueue = new PriorityQueue<>(((o1, o2) -> {
			return o1.point - o2.point; // point 기준 오름차순 정렬
		}));

		PriorityQueue<Node> rightQueue = new PriorityQueue<>(((o1, o2) -> {
			return o2.point - o1.point; // point 기준 내림차순 정렬
		}));

		while(N-- > 0){
			st = new StringTokenizer(br.readLine());
			int point = Integer.parseInt(st.nextToken());
			int cnt = Integer.parseInt(st.nextToken());
			if(point < S){
				leftQueue.add(new Node(point, cnt)); // 학교보다 왼쪽에 있다면
			}else{
				rightQueue.add(new Node(point, cnt)); // 학교보다 오른쪽에 있다면
			}
		}

		long length = 0;
		long total;
		while(!leftQueue.isEmpty()){ // 왼쪽 큐부터 검사
			Node cur = leftQueue.poll(); // 제일 끝 노드 꺼내기
			total = K; // 버스 정원 수 설정
			length += Math.abs(S - cur.point) * 2; // 제일 끝 노드는 무조건 방문해야함
			if(cur.cnt > total){ // 만약 버스에 태울 수 있는 인원보다 크다면
				cur.cnt -= total; // 남은 학생수를 계산
				leftQueue.add(cur); // 다시 큐에 넣음
				continue;
			}else{
				total -= cur.cnt; // 모두 버스에 태울 수 있다면, 버스 남은 좌석 수 계산
			}
			while(!leftQueue.isEmpty()){
				Node next = leftQueue.poll(); // 그 다음 끝 노드 꺼내기
				if(next.cnt > total){ // 만약 버스에 태울 수 있는 인원보다 크다면
					next.cnt -= total; // 남은 학생 술르 계산
					leftQueue.add(next); // 다시 큐에 넣음
					break;
				}else{
					total -= next.cnt; // 모두 버스에 태울 수 있다면, 버스 남은 좌석 수 계산
				}
			}
		}

		while (!rightQueue.isEmpty()) { // 오른쪽 큐 검사 시작
			Node cur = rightQueue.poll(); // 제일 끝 노드(가장 먼 아파트) 꺼내기
			length += Math.abs(S - cur.point) * 2; // 제일 끝 노드는 무조건 방문해야 함
			total = K; // 버스 정원 수 설정

			if (cur.cnt > total) { // 만약 버스에 태울 수 있는 인원보다 크다면
				cur.cnt -= total; // 남은 학생 수 계산
				rightQueue.add(cur); // 다시 큐에 넣음
				continue;
			} else {
				total -= cur.cnt; // 모두 버스에 태울 수 있다면 버스 남은 좌석 수 계산
			}

			while (!rightQueue.isEmpty()) {
				Node next = rightQueue.poll(); // 그 다음 끝 노드 꺼내기
				if (next.cnt > total) { // 만약 버스에 태울 수 있는 인원보다 크다면
					next.cnt -= total; // 남은 학생 수 계산
					rightQueue.add(next); // 다시 큐에 넣음
					break;
				} else {
					total -= next.cnt; // 모두 버스에 태울 수 있다면 버스 남은 좌석 수 계산
				}
			}
		}


		System.out.println(length);
	}

	static class Node{
		int point; // 위치
		int cnt; // 학생 수

		public Node(int point, int cnt){
			this.point = point;
			this.cnt = cnt;
		}
	}
}

---

문제 풀이 전략 

 

이 문제는 각 아파트에서 학교까지 통학버스를 보내며, 이동 거리를 최소화하는 문제다.
핵심은 왼쪽과 오른쪽을 완전히 독립된 문제로 나누고,
각 방향에서 가장 먼 집부터 버스에 태우는 방식으로 처리하는 것이다.

 

💡 핵심 아이디어

1. 학교 기준 왼쪽 / 오른쪽 아파트를 분리한다.
   → 서로 반대 방향이므로 버스는 완전히 독립적으로 움직인다.
2. 각 방향에서 “가장 먼 지점부터” 태운다.
   → 멀리 있는 학생을 방문하는 순간 왕복 거리(= 거리 × 2)가 확정된다.
3. 버스 정원 K만큼 채울 때까지 가까운 지점으로 이동하며 학생을 태운다.
4. 태워야 할 학생이 남아 있다면 같은 길을 다시 왕복한다.
   → 그래서 “가장 먼 지점을 기준으로 왕복 횟수가 결정된다”.

 

⭐️ 왜 PriorityQueue를 쓰는가?

• 왼쪽: 학교에서 가장 먼 집부터(가장 작은 좌표)
• 오른쪽: 학교에서 가장 먼 집부터(가장 큰 좌표)
  를 빠르게 꺼내기 위해서다.

각 방향을 다음 절차로 반복한다:

1. 가장 먼 지점 꺼냄
2. 그 지점까지 왕복 거리 추가
3. 남은 정원 안에서 학생 태움
4. 정원이 부족하면 다시 큐에 넣고 반복