[BOJ] 13335 - 트럭

풀어보기

접근

1. 다리로 접근하는 트럭의 순서는 바꿀 수 없다.
2. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 $L$보다 작거나 같아야 한다.
3. 무게의 합을 계산할 때 다리 위에 완전히 올라가지 못한 트럭은 포함하지 않는다.

결국 어떤 시점 $t_i$에 대기중인 트럭 $T_i$가 다리를 올라갈 수 있는지 판단하는 문제라고 볼 수 있겠다.

다리를 건너는 것은 어떻게 구현할 수 있을까? 필자는 파이썬의 deque를 활용하여 시점 $t_i$에 한 쪽 끝에서 다리를 건널 트럭 $T_i$를 집어넣으면 다른 쪽 끝에서 다리를 모두 건넌 트럭 $T_j$가 나오는, 마치 컨베이어 벨트와 같은 모습을 생각해보았다.
이렇게 하면 다리 위를 이동하는 것을 별도로 고려하지 않고 passing_trucks의 양쪽 끝만 신경써도 잘 굴러가는 것을 다음 코드를 통해 확인할 수 있다.

코드

from sys import stdin
from collections import deque

N, W, L = map(int, stdin.readline().split())
EMPTY = 0

waiting_trucks = deque(int(i) for i in stdin.readline().split())
passing_trucks = deque(EMPTY for _ in range(W))
current_load = 0
time_elapsed = 0

while current_load != 0 or waiting_trucks:
    current_load -= passing_trucks.popleft() # 다리를 다 건넌 트럭 배출
    
    next_truck = EMPTY
    if waiting_trucks and waiting_trucks[0] + current_load <= L: # 다음 트럭이 올 수 있는 경우
        next_truck = waiting_trucks.popleft()
        current_load += next_truck

    passing_trucks.append(next_truck)

    time_elapsed += 1

print(time_elapsed)

current_load는 passing_trucks의 양 쪽 끝을 감시하여 현재 다리에 가해지는 부하의 양을 저장한다. while문 내 조건문에서 다음 트럭이 현재 건널 수 있는지 검사하여 가능한 경우 트럭을 다리로 보낸다. 이 반복의 종료 조건은 다리에 부하가 0이고 트럭 대기열 waiting_trucks가 비어 있는 경우이다.
다리 위에 완전히 올라가지 않은 트럭은 무게 계산에서 제외한다고 했으므로, 반복문 내에서 먼저 다리에서 내려올 트럭을 처리한 다음 다리에 올라갈 트럭을 처리하도록 하였다.