BOJ 13335 - 트럭

문제

백준 온라인 저지 - 13335번

풀이 과정

다리에 무게 제한이 있을 때 모든 트럭이 다리를 건너서 다른 지역으로 넘어가는 최단 시간을 찾는 문제입니다.

현재 다리에 존재하는 모든 트럭의 무게를 추척하고 트럭의 시간을 별도의 배열로 관리해서 구현했습니다.
여기서 next 변수는 현재 다리를 건너기 위해 대기중인 트럭을 나타냅니다.

코드

import sys
from collections import deque

N, W, L = list(map(int, sys.stdin.readline().split()))
weights = list(map(int, sys.stdin.readline().split()))


def solution():
    goal, next = W + 1, 1
    on_bridge = deque([[1, weights[0]]])
    on_weight = weights[0]
    answer = 1

    while on_bridge:
        answer += 1

        for truck in on_bridge:
            truck[0] += 1

        if on_bridge[0][0] == goal:
            on_weight -= on_bridge[0][1]
            on_bridge.popleft()

        if next < N and weights[next] + on_weight <= L:
            on_bridge.append([1, weights[next]])
            on_weight += weights[next]
            next += 1

    return answer


print(solution())