[BOJ] 트럭 - 13335 (S1)

시간 제한	메모리 제한
1 초	512 MB

문제

트럭 여러 대가 다리를 건너려고 한다. 다리는 길이 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)