[백준 13335] 트럭

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n개의 트럭이 건너가려고 한다. 다리 위에는 w대의 트럭만 동시에 올라갈 수 있고 다리의 길이는 w 단위길이, 각 트럭들은 하나의 단위시간에 하나의 단위길이만큼 이동할 수 있다.

또한, 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L이하여야한다. 다리의 길이와 다리의 최대하중, 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때 모든 트럭이 다리를 건너는 최단시간을 구하라.

 

입력

첫째 줄에 트럭의 수 N, 다리의 길이 W, 다리의 최대하중 L이 주어진다.

두 번째 줄에는 트럭의 무게가 N개 주어진다.

 

출력

모든 트럭들이 다리를 건너는 최단시간을 출력한다.

---

접근

처음에는 주어진 예시를 통해 직접 그려보면서 시뮬레이션을 해본다. 그리고 다리와 트럭들을 어떻게 모델링할지 생각하였다. 여기서 자료구조를 선택하게되었고 다리와 트럭들을 큐에 넣기로 결정을 하였다. 

그리고 다리를 위한 큐에는 W만큼 0을 넣은 후에 시뮬레이션을 시작한다. 이후 매초마다 다음 순서로 처리한다.

- 다리에서 수를 하나 뺀다.

- 다리에 원소가 W미만으로 있다면 다음 트럭을 넣을 수 있는지 검사한다.

- 현재 다리의 합과 다음 트럭을 더했을 때 L이하라면 트럭을 넣고

- 아니라면 0을 넣는다.

 

위와 같은 생각으로 코드를 미리 손으로 작성하였고 작성하면서 잘못된 부분을 수정할 수 있었다.

 

구현

- 트럭의 무게를 입력받아 큐로 사용할 수 있도록 변환한다.

N, W, L = map(int, input().split())
trucks = deque(list(map(int, input().split())))

 

- 다리를 나타내는 큐에도 W만큼 0을 채운다. 이렇게하면 단위시간만큼 이동하는 것을 쉽게 구현할 수 있다.

- answer는 최종적인 해를 저장할 변수이다.

answer = 0
bridge = deque([0 for _ in range(W)])

 

- 트럭에 원소가 모두 사라질 동안 아래의 과정을 반복한다.

- 다리의 맨 앞에있는 트럭(0일 수도)을 제거한다.

- 제거했을 때 다리위에 존재하는 원소가 W미만일 때 원소를 추가한다.

- 원소를 추가할 때는 다리의 원소들의 합과 다음 진입할 트럭을 더했을 때 L이하면 트럭을 넣고

- 아니라면 0을 넣어 다리의 길이를 유지한다.

- 위 과정을 반복할 때마다 answer을 1증가시킨다.

while trucks:
    bridge.popleft()
    if len(bridge) < W:
        if sum(bridge) + trucks[0] <= L:
            truck = trucks.popleft()
            bridge.append(truck)
        else:
            bridge.append(0)
    answer += 1

 

- 최종적으로 answer에 W를 증가하여 반환한다.

- 왜냐하면 마지막에 진입한 트럭이 아직 다리를 건너지 못했는데 종료되었기 때문이다.

- 즉, 마지막 트럭이 건너는 시간을 합친 것이다.

answer += W
print(answer)

---

전체 코드

import sys
from _collections import deque
input = sys.stdin.readline

N, W, L = map(int, input().split())
trucks = deque(list(map(int, input().split())))

answer = 0
bridge = deque([0 for _ in range(W)])

while trucks:
    bridge.popleft()
    if len(bridge) < W:
        if sum(bridge) + trucks[0] <= L:
            truck = trucks.popleft()
            bridge.append(truck)
        else:
            bridge.append(0)
    answer += 1
answer += W
print(answer)