[백준 13335번] 트럭

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

import sys

input = sys.stdin.readline

from collections import deque

# 강을 가로지르는 하나의 차선으로 된 다리
# 이 다리를 n 개의 트럭이 건너가려고 한다
# 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다.

# 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 

# 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정

# 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다.

# 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정

# n - 다리를 건너는 트럭의 수 / w - 다리의 길이 / L - 다리의 최대하중
n, w, l = map(int,input().split())

weights = list(map(int,input().split()))

weights = deque([(x,w) for x in weights])

area = deque([])

time, current_weight = 0, 0

available = l

while True:
    
    if current_weight == 0 and len(weights) <= 0 and len(area) <= 0:
        break

    if area and area[0][1] <= 0:
        current_weight -= area[0][0]
        area.popleft()
        available += 1

    if weights and available > 0 and weights[0][0] + current_weight <= l:
        current_weight += weights[0][0]
        area.append(weights[0])
        weights.popleft()
        available -= 1
    
    for i in range(len(area)):
        area[i] = (area[i][0], area[i][1]-1)

    time += 1

print(time)

 

이번 문제는 n개의 트럭이 길이가 w인 다리를 건너려고 하는데, 다리가 견딜 수 있는 무게가 l 이라고 하였을 때 모든 트럭이 건널 수 있는 최단 시간을 구하는 문제이다.

 

출근길에 푼 문제라 정신없이 풀었지만, 먼저 문제를 풀기 위해서는 현재 다리가 견디고 있는 무게(current_weight)와 현재 다리에 남아있는 자리수(available)이라는 변수가 필요하다고 생각했다.

 

그리고 가장 중요한 것은 현재 남아있는 트럭들(weights)과 다리에 올라가 있는 트럭들(area)을 앞에서부터 차례대로 이동시켜야 하기 때문에 큐(Queue) 자료구조를 활용하였다.

 

자세한 로직은 다음과 같다.

1. 먼저 다리에 올라가 있는 맨 앞의 트럭(area[0])이 다리의 길이만큼 움직였을 때(area[0][1] <= 0) 해당 트럭을 popleft() 해준 뒤 다른 값들(current_weight, available)을 업데이트 해주었다.
2. 동시에 남은 트럭들 중 맨 앞의 트럭의 무게(weights[0][1])과 현재 무게(current_weight)의 합이 최대하중 L보다 작거나 같은 경우에는 해당 트럭을 큐에 삽입해주고 다른 값들(current_weight, available)을 업데이트 해주었다.
3. 마지막으로 종료조건으로는 '현재 견디고 있는 무게가 0이고, 남은 트럭과 다리에 올라가 있는 트럭이 모두 없는 경우' while 문을 종료해주었다.

큐를 활용하면 간단하게 풀이할 수 있는 구현문제였다 :)