백준[2513] 통학버스 (Python3)

2023 카카오 코테 2번? 하고 똑같다.
코테에서도 무난하게 풀어서 그런지, 생각보다 큰 어려움은 없었다.

지문을 분석해 보면, 버스는 가장 먼 거리에 있는 아이들을 우선으로 태우는 것이 유리하다.
또한, 버스 정원을 다 채우기 위해 왼쪽 오른쪽 왔다 갔다 할 필요가 없다.

학교를 기준으로 왼쪽, 오른쪽에 대한 큐 2개를 만들었다.
단지의 위치가 학교보다 왼쪽에 있다면, (학교 위치 - 단지 위치, 학생 수) 형태로 넣고
학교보다 오른쪽에 있다면, (단지 위치 - 학교 위치, 학생 수) 형태로 넣는다.
그 후 위치 값을 기준으로 정렬한다.

그 후, 단지의 학생 수와 버스 정원을 비교해, 다 태울 수 있다면, 해당 단지에 대한 정보를 pop 하고,
다 태우지 못하면 남은 정원만큼 학생 수를 차감하는 식으로 푼다.

이동 거리는, 처음에 학생을 태운 곳이 항상 먼 거리가 되기 때문에,
이 값을 * 2 해주면서 더해준다.

 

from collections import deque

N, K, S = map(int, input().split())
left, right = deque(), deque()
for _ in range(N):
    a, b = map(int, input().split())
    if a < S:
        left.append((S - a, b))
    else:
        right.append((a - S, b))

left = sorted(left, key=lambda x: x[0])
right = sorted(right, key=lambda x: x[0])

answer = 0
while left:
    remain, distance = K, 0
    while remain > 0 and left:
        a = left.pop()
        if remain >= a[1]:
            remain -= a[1]
        else:
            left.append((a[0], a[1] - remain))
            remain = 0
        distance = max(distance, a[0])
    answer += distance * 2

while right:
    remain, distance = K, 0
    while remain > 0 and right:
        a = right.pop()
        if remain >= a[1]:
            remain -= a[1]
        else:
            right.append((a[0], a[1] - remain))
            remain = 0
        distance = max(distance, a[0])
    answer += distance * 2
print(answer)