BOJ-13335 트럭

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

문제 소개

강을 가로지르는 다리를 n개의 트럭이 건너가려고 한다. 다리 위에는 w개의 트럭만 동시에 올라갈 수 있으며, 다리 위에 올라간 트럭들의 무게의 합은 l보다 작거나 같아야 한다.

각 트럭은 하나의 단위시간에 하나의 단위길이만큼만 이동할 수 있으며, 트럭의 순서는 바뀌지 않는다.

문제 풀이

다리 위에 올라간 트럭들의 무게와 남은 거리에 대한 정보를 담기 위해 큐를 사용하였다.

• queue[x][y]는 무게가 x인 트럭이 다리를 건너기까지 남은 거리가 y임을 뜻한다.

• time은 트럭들이 단위길이를 이동할 때마다 누적되는 시간이다. 최종값을 해답으로써 출력하게 된다.

• cnt는 다리를 건너간 트럭의 개수이다.

• i는 몇 번째 트럭이 다리에 올라올 차례인지를 나타내는 변수이다.

트럭을 이동시키는 일련의 동작은 모든 트럭이 다리를 건널 때까지 반복한다.

1. 다리가 비어있는 경우 : 다음 트럭을 다리에 추가한다.

2. 다리가 비어있지 않은 경우

   1. 시작점에 트럭이 남아있지 않은 경우 : 마지막 트럭의 정보를 통해 time의 값을 계산한다.
   2. 그 외의 경우 : 트럭들을 한 칸씩 이동시키고 다리가 비게 된다면 즉시 트럭을 추가한다. 그리고 하중에 여유가 있다면 다음 트럭을 추가하고, 여유가 없다면 continue한다.

코드

from sys import stdin
from collections import deque
input = lambda: stdin.readline().rstrip()

n, w, l = map(int, input().split())
truck = list(map(int, input().split()))

queue = deque([], maxlen=w)

time = 0
cnt = 0
i = 0

# 모든 트럭이 다리를 건널 때까지
while cnt < n:
    # 다리가 비었다면
    if not queue:
        queue.append([truck[i], w])
        time += 1
        # print(queue, time)
        i += 1
    # 다리가 비어있지 않다면
    else:
        if cnt + len(queue) == n:
            time += queue[-1][1]
            break

        for j in queue:
            j[1] -= 1
        time += 1
        if queue[0][1] == 0:
            queue.popleft()
            cnt += 1
            # 다리가 비었으면 트럭 추가
            if not queue:
                time -= 1   # 중복으로 time이 증가하지 않도록 하기 위함
                continue

        # 여유가 있다면
        if sum(info[0] for info in queue) + truck[i] <= l:
            queue.append([truck[i], w])
            # print(queue, time)
            i += 1
        # 여유가 없다면
        else:
            # print(queue, time)
            continue

print(time)

주석 처리한 3개의 print()문을 통해 각 time마다 다리의 상황을 확인할 수 있다.