본문 바로가기
백준 알고리즘/Python

[백준] 13335. 트럭 - Python

by 리버🐦‍🔥 2023. 9. 26.

[Silver I]

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

 

13335번: 트럭

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트

www.acmicpc.net

풀이

  1. 다리를 건너기 전 트럭들을 큐에 넣는다.
  2. 다리를 건너는 중인 트럭을 큐에 넣는다. (큐에 넣을때는 다리를 다 건널 때 까지 남은 시간을 같이 넣어준다.)
  3. 다리를 건너기 전 큐와 다리를 건너는 중인 큐에 있는 트럭이 모두 없어질 때까지 남은 시간을 1씩 줄이며 (1)~(2)과정을 반복한다.
from collections import deque
import sys

# global var
n = 0
w = 0
l = 0
before = deque()
onBridge = deque()
ans = 0

def solve():
    global n, w, l, ans, before, onBridge
    finished = 0
    weightSum = 0
    while finished != n:
        # 다리 위에 트럭이 있으면
        if onBridge:
            # 아직 트럭이 다리를 건너는 시간이 지나지 않았다면
            if onBridge[0][1] < 1:
                weightSum -= onBridge[0][0]
                finished += 1
                onBridge.popleft()

        # 아직 다리에 진입하지 못한 트럭이 있으면
        if before:
            # 다음 들어갈 트럭의 무게 + 다리 위의 트럭들의 무게가 다리의 최대 하중보다 작다면
            if weightSum + before[0] <= l:
                weightSum += before[0]
                onBridge.append([before.popleft(), w])

        for car in onBridge:
            car[1] -= 1

        ans += 1

# main
n, w, l = map(int, sys.stdin.readline().split())

before = deque(list(map(int, sys.stdin.readline().split())))

solve()

print(ans)