개인적인 느낌으로, 지금까지 올라온 문제 중에 가장 어려웠습니다.
문제에서 주어진 내용을 바탕으로 잘 구현하면 풀리지만, 그 과정이 쉽지가 않았습니다.
저는 다리 위의 차량의 정보를 저장할 bridge와 다리에 진입하기 원하는 queue라는 이름의 두 개의 deque을 이용하여 문제를 해결하였습니다.
핵심 아이디어는 '다리 위에 있는 시간을 기록해 두자.'와 '먼저 빠져나온 뒤, 새로 들어가라' 인 것 같습니다.
while 문으로 무한 루프를 돌게 하였고, 종료 조건으로 queue와 bridge가 모두 비었으면 종료하도록 하였습니다.
먼저, 매 시간마다 다리 위에 있는 차량들의 시간 변수들을 증가시켜 주었습니다. (리스트의 두 번째 요소가 시간입니다.)
1초마다 왼쪽으로 1씩 움직이므로, 다리 위에 있는 시간이 다리 길이보다 길어지면, 다리를 건넜다는 것을 의미하므로, 바로 bridge의 첫번째 요소를 pop 해줍니다. (먼저 pop을 해 줘야, 새로 진입할 차량이 들어올 수 있습니다.)
total_weight라는 변수를 0으로 초기화 하였고, 다리 위의 차량의 무게를 모두 더하였습니다.
다리 위의 차량이 모두 비어있으면(not bridge), 0으로 초기화하였고, 그렇지 않다면 각 리스트의 첫째 요소를 더했습니다.
(첫째 요소가 무게, 두번째 요소가 다리 위에 있는 시간을 의미합니다.
만약, 다리에 진입하기 원하는 차량이 queue에 존재한다면, (if queue)
queue의 첫째 요소(queue[0])과 total_weight를 더하여 다리의 최대하중 L보다 작거나 같으면
queue에서 popleft를 하여, bridge에 리스트 형식으로 (값이 시간마다 변해야 하므로 튜플은 사용하지 않았습니다)
[queue의 첫요소를 저장한 변수, 1] 로 bridge에 append 해주었습니다. 즉, 다리에 진입하였음을 의미합니다.
마지막에는 time이라는 변수를 1씩 증가시켜 주었고, while문을 빠져나오면 time을 출력합니다.
from collections import deque
from sys import stdin
n, w, L = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
time = 0
bridge = deque()
total_weight = 0
queue = deque(arr)
while True:
if not bridge and not queue: # 다리와 큐가 모두 비었으면 종료.
break
total_weight = 0 # 다리 위에 있는 차량의 무게를 저장하는 변수입니다.
if bridge:
for i in range(len(bridge)):
bridge[i][1] += 1 # 다리에 있는 모든 요소의 시간을 1씩 증가시켜 준다.
if bridge[0][1] > w: # 다리에 있는 시간이 다리의 길이보다 커지면, 통과된 것임.
bridge.popleft() # 그런 차량은 bridge에서 pop 해준다.
# pop 해주는 과정이, 새로 들어오는 과정보다 먼저여야 합니다.
# 차량이 나가면서 동시에 들어올 수 있는데, 먼저 나가지 못하면 새로운 차량이 들어올 수 없습니다.
if not bridge: # 다리가 빈 경우, 다리 위의 차량의 무게는 0입니다.
total_weight = 0
else: # 그 외의 경우, 차량의 무게를 모두 더합니다.
for i in range(len(bridge)):
total_weight += bridge[i][0]
if queue and total_weight + queue[
0] <= L: # 큐에 차량이 남아있으며, 새로운 차량이 다리 위에 올라와도 최대 중량보다 같거나 적으면, 큐에서 하나를 뽑아 다리 위에 올립니다.
a = queue.popleft()
bridge.append([a, 1])
time += 1
print(time)