[Python] 백준 13335번 - 트럭

📖 문제

13335번: 트럭

 

🔎 풀이

큐를 이용하여 푸는 문제입니다.

 

초기 리스트에는 다리 위 공간을 모두 0으로 채워줍니다. 이때 매번 리스트 합을 계산하여 무게를 구하면 비효율적입니다. 때문에 따로 변수를 생성하여 트럭이 다리 위로 진입하면 트럭의 무게를 더해주고, 나가면 빼줍니다. 만약 트럭이 더 이상 다리에 진입하지 못하는 경우에는 리스트에 0을 추가해줍니다.

 

💻 코드

import sys
import collections
input = sys.stdin.readline

n, w, L = map(int, input().split())
truck = list(map(int, input().split()))
# 트럭이 없는 경우 0으로 채우기
bridge = collections.deque([0] * w)
# 다리 위 무게 합
sum_weight = 0
# 트럭 index
id = 0
cnt = 0
# 통과한 트럭
pass_truck = 0

while (pass_truck != n):
    cnt += 1
    # 선입선출 구조인 큐를 이용
    p_truck = bridge.popleft()
    # 값이 0이 아닌 경우 트럭이므로 통과한 트럭 증가
    if p_truck: pass_truck += 1
    # 통과한 트럭은 다리 위 무게에서 차감 (트럭이 아닌 경우 0이기에 값 변화 없음)
    sum_weight -= p_truck
    
    # 다리 위 무게와 지나갈 트럭 무게의 합이 L보다 작거나 같은 경우
    if id < n and sum_weight + truck[id] <= L:
        bridge.append(truck[id])
        sum_weight += truck[id]
        id += 1
    # 위 조건을 만족하지 못한 경우 빈 공간인 0 추가
    else:
        bridge.append(0)

print(cnt)