문제
강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.
예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.
Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.
다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.
입력
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.
출력
출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.
예제 입력 1
4 2 10
7 4 5 6
예제 출력 1
8
풀이
문제를 보았을 때, 다리가 큐처럼 느껴졌다. 그러나 가장 큰 문제는 다리의 길이는 고정인데, 큐는 고정이 아니라는 것이다. 그리고 큐에서는 다리 위의 트럭이 없는 부분, 즉 공백을 구현할 수 없기 때문에 이를 어떻게 처리할지 고민이었다.
뭔가 길이가 고정인 파이썬에 있을 것 같아서 찾아보았고, maxlen 속성으로 고정 길이 데크(큐로 사용)를 생성할 수 있다는 것을 알게 되었다. 이렇게 다리를 구현했고, 트럭이 지나가는 동작을 구현하기 위해 큐에 건너는 트럭의 무게를 삽입하기로 하였고, 다리 위 트럭이 지나가지 않는 부분은 0으로 표현하기로 했다(초기값은 큐에 0을 전부 채움). 이렇게 하면 다리위에 트럭이 아예 없는 경우, 즉 다리를 다 건넌 경우에 큐의 합이 0이 되기 때문에 이를 통해 동작(while문)의 종료 조건을 지정할 수 있었다. 대기중인 트럭도 큐를 사용했기 때문에 이 문제에서는 2개의 큐를 사용했다.
로직은 다음과 같다.
먼저, 초기화로 큐에 제일 앞 트럭 1대를 넣고, 시간을 1로 설정한다(트럭이 처음에 움직임)
1. 제일 앞 트럭(없을 수도 있음)을 제외한 나머지 트럭의 합 + 대기 중인 제일 앞 트럭의 무게가 L을 초과하면 0을 삽입 *위 동작을 통해 제일 앞 부분을 다리를 건넘으로 처리(트럭이 없을 수도 있음)
2. 무게가 L을 초과하지 않으면 대기중인 제일 앞 트럭을 삽입한다.
3. 시간을 1 증가시킨다.
3. 다리위 트럭이 없어질 때까지(= 큐의 합이 0일때까지 = 다리를 다 건널때까지) 1-3을 반복
다리를 큐로 표현한다는게 되게 생소했고(고정 길이로 설정해야 했기 때문), 다리의 비어있는 부분을 0으로 처리함과 동시에 다리 위의 이동을 0을 삽입함으로서 전체가 왼쪽으로 이동하여 제일 앞부분이 다리를 건너게 된다는 부분도 나름 잘 표현한 것 같았다.
import sys
from collections import deque
n, w, L = map(int, input().split())
queue_bridge = deque(maxlen=w)
queue_truck = deque()
# 다리 초기화
for _ in range(w):
queue_bridge.append(0)
# 트럭 초기화
for weight in map(int, input().split()):
queue_truck.append(weight)
# 첫번째 트럭 삽입 및 시간 카운트+1
queue_bridge.append(queue_truck.popleft())
time = 1
# 트럭 삽입(큐 합이 0이면, 즉 다 지나가면 빠져나옴)
print(queue_bridge)
while sum(queue_bridge) != 0:
# ---- 다음 트럭을 넣을지 말지를 판단 ----
# 제일 앞 트럭 지나간 후에
# 총 무게 합이 다리의 최대 하중보다 작으면
# 다음 트럭 넣음
if len(queue_truck) != 0:
if sum(list(queue_bridge)) - queue_bridge[0] + queue_truck[0] > L:
queue_bridge.append(0)
else:
queue_bridge.append(queue_truck.popleft())
else:
queue_bridge.append(0)
time+=1
print(time)