[백준 13335번] 트럭 - 파이썬

https://www.acmicpc.net/problem/13335

13335번: 트럭

 

💡문제 분석 요약

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

 

💡알고리즘 설계

1. 트럭을 deque로 저장하고, 다리를 다리의 길이 만큼 0으로 채운 deque로 설정한다.

2. 시간이 1씩 늘어날 때 마다, 다리에서 가장 앞에 있는 요소를 삭제한다.

3. 다리의 맨 뒤에, 가장 앞에있는 트럭 혹은 0을 붙인다.

3-1. 다리 위에 있는 트럭의 총 무게와 가장 앞에 있는 트럭의 합이 최대 하중보다 같거나 작을 경우만 가장 앞에 있는 트럭을 붙인다.

4. 모든 트럭이 다리에 진입하고, 다리 위에 있는 트럭의 무게의 합이 0일 경우 중단한다.

 

💡코드

import sys
input = sys.stdin.readline

from collections import deque
n, w, L=map(int, input().split())
#n: 트럭 개수, w: 다리 길이, L: 최대 하중

truck=deque(list(map(int, input().split())))
bridge=deque([0 for _ in range(w)])

time=0
weight=0
while True:
    weight-=bridge.popleft()

    if not truck or weight+truck[0]>L:
        bridge.append(0)
    else:
        new_truck=truck.popleft()
        bridge.append(new_truck)
        weight+=new_truck
        
    time+=1

    if not truck and weight==0:
        break

print(time)

 

💡 느낀점 or 기억할 정보

처음엔 weight 대신 sum(bridge)를 이용했는데, 시간이 오래 걸려 weight 변수를 만든 후 재채점했다. 시간이 30ms 줄어들었다..

list를 이용하고 pop(0)을 해도 되지만 pop(0)은 시간복잡도가 O(N)이 걸려 deque이 더 빠를 것 같아 deque를 이용했다.