[백준 13335번] 트럭

박형진·2023년 2월 20일
0

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

1. 코드

import sys
from collections import deque

n, w, l = map(int, sys.stdin.readline().rstrip().split())
trucks = deque(map(int, sys.stdin.readline().rstrip().split()))
target = sum(trucks)

q = deque([0] * w)
cnt = 0
weight = 0
time = 0
complete = 0
while True:
    if complete == target:  # 모든 트럭이 다리를 건넌다면
        break
    time += 1

    q.append(0)
    out = q.popleft()

    if out != 0:
        complete += out  # 현재 트럭은 다리를 건넘
        cnt -= 1
        weight -= out

    if trucks and trucks[0] + weight <= l and cnt+1 <= w:  # 트럭이 다리에 진입 가능하다면
        truck = trucks.popleft()
        q[-1] = truck
        cnt += 1
        weight += truck

print(time)

2. 후기

deque 의 rotate 메서드를 활용하는 풀이도 있지만, 매 rotate 당 O(n)이 소요되기 때문에 좋은 방법은 아니다.

q.append(0)
out = q.popleft()

"""
1. [0, 1, 0] 
   [0, 1, 0, 0] : q.append(0)
   [1, 0, 0] : q.popleft()

2. [1, 0, 0]
   [1, 0, 0, 0] : q.append(0)
   [0, 0, 0] : q.popleft()

3. [0, 0, 0]
	...
"""

인덱스가 초과되어 다시 첫 번째 인덱스로 넘어가는 부분은 제외하고 rotate(-1)과 동일하게 작동하는 코드이다.

profile
안녕하세요!

0개의 댓글