⚠️ 문제
https://www.acmicpc.net/problem/13335
🔐 풀이
트럭들이 다리를 지나감에 따라 시간대별로 다리 위의 트럭 무게를 누적해 문제를 해결했습니다.
문제의 첫 번째 예시를 이용해서 설명하자면,
우선 아래와 같이 시간대별 다리 위 트럭 무게를 0으로 초기화해줍니다.
이 때 0초는 -1로 설정하는데, 이는 나중에 모든 트럭이 다리를 건너는 시점을 무게 0을 통해 찾기 위함입니다.
트럭이 다리에 올라가게 되면 다리의 길이 (w)인 2초동안 다리에 존재하게 됩니다.
따라서 첫 번째 무게 7인 트럭이 올라가면 아래와 같이 트럭이 다리 위에 존재하는 1, 2초에 무게를 누적합니다.
이제 두 번째 무게 4인 트럭이 올라가야 하는데, 만약 다리의 최대 하중이 11 이상이라면 앞선 무게 7의 트럭과 함께 다리에 올라가있을 수 있습니다. 하지만 다리의 최대 하중이 10이기 때문에 무게 4인 트럭은 아래와 같이 앞선 트럭이 다리에서 벗어나는 3초에 올라갈 수 있습니다.
다음 무게 5인 트럭은 앞선 무게 4인 트럭과 합이 다리의 최대하중보다 작기 때문에 다리에 함께 올라가있을 수 있습니다. 따라서 앞선 무게 4의 트럭이 한칸(1초) 이동했을 때 바로 따라 올라갈 수 있어 이때부터 무게를 누적합니다.
마지막 무게 6인 트럭은 무게 5인 트럭과 함께 올라갈 수 없기 때문에 무게 5인 트럭이 다리를 벗어나는 6초에 다리에 올라가게 됩니다.
이렇게 모든 트럭이 지나가고, 그 최단시간은 아래와 같이 처음 다리 위 트럭 무게가 0이 되는 시점입니다.
🧑🏻💻 코드
import sys
n, w, l = map(int, sys.stdin.readline().split())
truck = list(map(int, sys.stdin.readline().split()))
bridge = [0] * (n * w + 2)
bridge[0] = -1
time = 1
for weight in truck:
# 트럭이 다리에 올라갈 수 있는 시간을 구하기
# (최소 : 앞 트럭 1초 뒤)
# (최대 : 앞 트럭이 다리에서 빠져나간 후)
while bridge[time] + weight > l:
time += 1
# 트럭이 다리에 올라가있는 시간동안 무게 누적
for i in range(time, time+w):
bridge[i] += weight
# 다음 트럭은 1초 뒤부터 가능
time += 1
# 다리에 올라가있는 트럭의 무게가 0이 될 때가 모든 트럭이 건넌 시점
print(bridge.index(0))