(Python/파이썬) - 백준(BOJ) 2513번 : 통학버스

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

2513번: 통학버스

---

• 문제 : 

주택난을 해결하기 위해서 직선 도로 하나를 따라 여러 아파트 단지들을 지었다. 또, 이 아파트 단지 주민을 위해 도로 위 한 지점에 학교 하나를 신설하였다. 아파트 단지들이 서로 멀리 떨어져 있기 때문에 반드시 통학버스를 이용해서만 다닐 수 있고, 통학버스는 한 대이다.

 

각각의 아파트 단지와 학교의 위치는 도로 위의 좌표로 주어지며, 또 각 아파트 단지마다 여기에 사는 학생들의 수도 주어진다. 통학버스는 아침에 학교를 출발하여 각 아파트 단지에 있는 학생들을 태우고 학교로 다시 돌아온다. 이 통학버스는 정원을 초과하여 학생을 태울 수 없고, 모든 학생을 등교시킬 때까지 이 과정을 반복한다. 

위 규칙을 따라서 모든 학생들을 학교에 등교시키는 예를 보자. 아파트 단지 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이 된다.

 

학교의 위치, 각각의 아파트 단지의 위치와 학생 수, 통학버스의 정원이 주어졌을 때, 모든 학생을 등교시키는데 필요한 통학버스의 총 이동 거리의 최솟값을 계산하는 프로그램을 작성하시오. 

 

 

 

---

• 풀이 :

그리디하게 풀 수 있는 문제였습니다.

 

문제 해결 아이디어는 아래와 같습니다.

 

가장 먼 아파트부터 태울 수 있는 최대 정원을 태워서 복귀한다.

 

구현입니다.

 

1. 학교를 기준으로 왼쪽 아파트, 오른쪽 아파트 묶음으로 나누어줍니다. 아파트의 좌표는 학교로부터의 거리로 갱신해줍니다.

 

2. 가장 먼 아파트부터 고려하기 위해 거리를 기준으로 내림차순 정렬합니다.

 

3. 태워야 할 아이가 남아있는 가장 먼 아파트(queue의 첫 번째 인덱스)에 갔다 오면서 거리가 먼 아파트부터 태울 수 있는 아이를 모두 태웁니다. 이 때, 버스가 이동한 거리는 가장 먼 아파트와의 왕복거리 한 번만 계산합니다.

 

4. 모든 아이를 태웠을 때 종료합니다.

 

 

 

---

• 소스코드 : 

import sys
from collections import deque
input = sys.stdin.readline


N, K, S = map(int,input().split())
left = []
right = []
for _ in range(N):
    x,y = map(int,input().split())
    if x > S:
        left.append([abs(S-x),y])
    elif x < S:
        right.append([abs(S-x),y])
left = deque(sorted(left,key = lambda x : x[0], reverse=True))
right = deque(sorted(right,key = lambda x : x[0], reverse=True))
curr = 0
answer = 0
while left:
    answer += (left[0][0] * 2)
    while left and left[0][1] <= K-curr: # 전부 실을 수 있는 경우
        d, h =left.popleft()
        curr += h
    if left: # 일부만 실을 수 있는 경우
        left[0][1] -= K-curr
        curr = 0
curr = 0
while right:
    answer += (right[0][0] * 2)
    while right and right[0][1] <= K - curr:  # 전부 실을 수 있는 경우
        d, h = right.popleft()
        curr += h
    if right:  # 일부만 실을 수 있는 경우
        right[0][1] -= K - curr
        curr = 0
print(answer)