[TIL] 백준 13335 - 트럭 ( python )

📌 문제 탐색하기

n = 트럭 개수

w = 다리 길이

L = 다리의 최대하중

 

다리 위에는 동시에 최대 w대의 트럭만 올라갈 수 있습니다.
다리 위의 트럭들의 총무게는 L을 초과할 수 없으며, 매 초마다 하나의 단위 길이(unit distance)만 이동해야 합니다.

트럭이 다리를 다 건너는 데 걸리는 최소 시간을 구하는 것이 핵심입니다.

 

n ≤ 1000

w ≤ 100

L ≤ 1000

 

가능한 시간복잡도

트럭이 다리를 건너는 과정은 초 단위로 진행됩니다.

최악의 경우, 1초에 1개의 트럭만 이동한다고 가정하면 O(n * w) 만큼 걸릴 수 있습니다.

하지만 w의 최대값이 100이므로 최악의 경우라도 1000 * 100 = 100,000번 연산입니다.

1초에 1천만 번 정도 처리하기에 시간 내에 충분히 처리 가능한 수준입니다. 

알고리즘 선택

큐(Queue)를 활용한 시뮬레이션 기법을 사용하면 트럭의 이동을 처리할 수 있습니다.

• 다리를 deque(큐)로 사용하여 다리 위 트럭을 관리합니다.
• 시간을 1초씩 증가시키면서 트럭을 이동시킵니다.
• 다리에 올라갈 수 있는 트럭인지 확인하여 추가합니다.
• 현재 다리 위의 트럭들의 무게 합을 유지하면서 새로운 트럭이 추가될 수 있는지 체크합니다.
• 모든 트럭이 다리를 완전히 건널 때까지 반복합니다.

---

📌 코드 설계하기

• 문제의 Input을 받습니다.
• 다리 상태를 deque로 관리합니다. ( 길이 w만큼 )
• 현재 다리 위의 총 무게를 weight로 유지합니다.
  • 새로운 트럭을 추가할 때 weight + truck <= L 인지 확인합니다.
• 트럭이 다리를 건너는 과정을 while문을 통해 시뮬레이션 합니다.
  • 트럭이 다리를 완전히 건널때까지 반복합니다.
  • 다리에서 가장 앞에 있는 트럭이 도착하면 제거합니다.( popleft() )
  • 새로운 트럭을 다리에 올릴 수 있는지 확인합니다.
    • 트럭이 다리에 올라갈 수 있다면
      • 다리에 새로운 트럭을 추가합니다. ( append(truck) )
      • weight에 truck의 무게를 추가합니다.
    • 트럭이 다리에 올라갈 수 없다면
      • 다리에 0을 추가하여 앞의 트럭이 건널 수 있는 시간을 만들어줍니다.
• 마지막 트럭이 다리를 완전히 건너야 하므로 마지막에 건너는 시간까지 포함하여 시간을 추가합니다. 
  • time += w
• 최종 구해진 시간을 출력합니다.

---

📌 정답 코드

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

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

bridge = deque([0] * w)
weight = 0
time = 0

for truck in trucks:
    while True:
        time += 1
        weight -= bridge.popleft()

        if weight + truck <= L:
            bridge.append(truck)
            weight += truck
            break
        else:
            bridge.append(0)

time += w

print(time)