https://acmicpc.net/problem/13335

풀이

그림에서 보고 큐를 사용해서 풀었다.
처음에 큐에 다리의 길이만큼 0을 다리의 길이를 표시해주었다. 차가 다리에 들어와서 나가기까지의 시간을 카운트할 수 있도록 빈 공간을 넣어준 것이다.

그리고 while 문을 돌면서 지금 차가 들어가도 다리 하중을 넘지 않는 경우에 큐에 새로운 차를 넣어주고 idx를 증가시켜준다.(위 그림에서 2번째, 4번째, 5번째 ... 상황) 그렇지 않은 경우에는 빈공간을 넣어준다. (위 그림에서 3번째 상황)

마지막에 아직 큐에 차가 남아 있는 경우 마지막 차가 다 나갈 때까지 pop 시켜주면서 시간을 증가시켜준다.

코드

from collections import deque

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


# 큐를 이용해서 구현
# 처음에 다리의 길이만큼 0을 넣어준다 -> 차가 다리에 들어와서 나가는 거 시간 카운트할 수 있도록 빈 공간을 넣어준다.
q = deque()
for _ in range(w):
    q.append(0)

time = 0


idx = 0
while idx < n:
    time += 1
    q.popleft()

    # 지금 차 들어가도 다리 하중이 넘지 않는 경우
    if sum(q)+cars[idx] <= L:
        q.append(cars[idx])
        idx += 1
    # 넘으면 이전 차만 앞으로 가는 거고 빈공간이 생기는 거니까 0 넣어줌
    else:
        q.append(0)

# 다리에 차가 다 나가야 하므로 큐가 빌때까지
while q:
    time += 1
    q.popleft()

print(time)