문제

트럭 여러 대가 다리를 건너려고 한다. 다리는 길이 w, 최대 하중 L이다. 모든 트럭이 다리를 건너는 최소 시간을 구하는 프로그램을 작성하시오.

풀이

큐를 사용한 시뮬레이션 문제이다.

코드

from collections import deque

n, w, L = map(int, input().split())
trucks = list(map(int, input().split()))

bridge = deque([0] * w)
t = 0
cur_w = 0
i = 0

while i < n:
    t += 1
    cur_w -= bridge.popleft()
    if cur_w + trucks[i] <= L:
        bridge.append(trucks[i])
        cur_w += trucks[i]
        i += 1
    else:
        bridge.append(0)

t += w
print(t)

시간 복잡도

O(n × w)