[백준/Python] 13335 트럭

 

📌 문제 분석하기

• 길이 w(1 ≤ w ≤ 100) 단위길이의 다리 위를 n(1 ≤ n ≤ 1,000)개의 트럭이 건너가고자 함
• 다리 위에는 w대의 트럭만 동시에 올라갈 수 있음
• 각 트럭은 하나의 단위시간 동안 하나의 단위길이 만큼 이동 가능
• 다리 위 트럭들의 무게 합 ≤ 다리 최대하중 L(10 ≤ L ≤ 1,000)을 만족해야 함
• 다리 위에 완전히 올라지 못한 트럭은 무게 계산 시 포함하지 않음
• 모든 트럭이 다리를 건너는 최단 시간 구하기

가장 먼저 다리 위에 올라간 트럭이 먼저 다리를 건너게 되므로, 큐(Queue) 자료구조를 사용할 수 있다. 트럭이 들어가지 않은 공간에는 0을 넣어 큐의 원소 개수를 다리의 길이인 w만큼 유지시키면서, 큐에 들어간 트럭의 무게합이 L을 넘어가지 않도록 다음 트럭을 큐에 넣고, 한칸씩 이동시키는 방법을 사용할 수 있다.

 

큐의 상태를 업데이트할 때는 맨앞, 맨뒤 요소의 삽입/삭제 연산만 일어나므로 collections.deque를 사용한다면 O(1)의 시간복잡도를 가지며, n개의 트럭이 각각 w길이의 다리를 건너야 하므로 총 O(n+w)의 시간복잡도를 가진다. 큐에 들어간 트럭의 무게합을 매번 계산하게 될 경우 O(w)의 시간이 추가적으로 소요되므로 시간복잡도는 O(w)*O(n+w)가 되는데, 별도의 큐에 들어간 트럭의 무게 합 변수를 두어 삽입, 삭제 연산이 일어날 때 갱신해주는 방법으로 최적화가 가능하다.

---

📌 코드 설계하기

1. 다리를 건너는 트럭의 수(n), 다리의 길이(w), 다리의 최대하중(L) 입력받기
2. 트럭들의 무게 정보(trucks) 입력받아 큐형태로 변환
3. 걸리는 시간을 계산할 변수(time) 초기화
4. 다리의 현재 하중을 계산할 변수(bridge_weight) 초기화 
5. 다리의 현재 상황을 나타낼 큐(bridge) 초기화
6. truck 큐에 트럭이 남아있거나, 다리에 올라간 트럭이 있는 동안 트럭 이동시키기
   1. 가장 먼저 bridge 큐의 맨 앞 원소를 제거하여 현재 다리 위에 있는 트럭을 한칸씩 이동
   2. 아직 다리 위에 올라오지 않은 트럭이 있다면(= trucks 큐가 비어있지 않다면)
      • 다리의 현재 하중과 다음으로 올라갈 트럭 무게의 합이 L을 넘지 않는다면 trucks 큐의 맨 앞 원소를 pop해서 bridge 큐에 push 
      • 그렇지 않다면(= 다음 트럭을 다리 위에 올릴 수 없다면) bridge에 0 삽입
   3. time 변수에 1 더하기
7. truck 큐가 비고, 다리에 올라간 트럭의 무게가 0이 되면, 총 소요시간 출력

 

---

📌 정답 코드

from collections import deque

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

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

while trucks or bridge_weight:
  bridge_weight -= bridge.popleft()
  if trucks:
    if trucks[0] + bridge_weight <= L:
      truck = trucks.popleft()
      bridge.append(truck)
      bridge_weight += truck
    else:
      bridge.append(0)
      
  time += 1

print(time)