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
문제는 하중과 길이가 제한된 다리를 무게가 다른 트럭들이 모두 지날 수 있는 최소시간을 구하는 문제다.
트럭이 먼저 들어온 순으로 나가기 때문에 큐를 활용할 생각을 했다. 단위 시간마다 수행되어야 할 일을 분리했다.
길이가 2 최대 하중이 10인 다리를 지나는 트럭의 예시를 보자.
무게가 7인 트럭이 다리에 올라가고 그 뒤로 4 트럭은 최대하중이 10이기 때문에 올라갈 수 없어서 기다린다. 그 뒤로 7 트럭이 나가고 동시에 4 트럭이 들어온다. 여기서 단위시간동안 해야 하는 일을 분리할 수 있다.
1 단위시간 동안 할 수 있는 것은 1. 만약 트럭 중에 나갈 준비가 된 트럭은 나간다. 2. 최대하중을 넘지 않았다면 트럭이 들어온다.
이렇게 분리를 하고 트럭이 기다리면서 생기는 공백은 다리에 -1 값을 가진 트럭이 있다고 생각하자. 위에서 나갈 준비가 된 트럭을 판단하는 것은 현재 큐 사이즈가 다리의 길이와 같아지는 것으로 판단하자.
트럭이 기다려야 하면 -1인 트럭을 q에 넣고, 마지막 트럭이 지난 후에도 -1인 트럭이 들어가야 하므로 트럭 배열에 다리 길이만큼의 -1 트럭을 미리 넣어둔다.
다리의 길이를 현재 queue 사이즈로 두고, 다리의 최대하중을 queue 원소들의 합(-1 유령트럭 제외)으로 두자.
while문 안에서 단위시간동안 하는 일을 분리하고, 만약 모든 일이 끝나고 현재 queue 원소들의 합이 0이 되면 break 한다.
queue를 활용해야 하지만 그냥 덱으로 풀어도 무방
import sys
from collections import deque
n,k,w = map(int,sys.stdin.readline().split())
truck = list(map(int,sys.stdin.readline().split()))
for i in range(k+1): truck.append(-1)
q = deque()
q.append(truck[0])
t = 1
curTruck = 1
qSize = truck[0]
while q:
if len(q) == k:
x = q.popleft()
if x != -1:
qSize-=x
if qSize + truck[curTruck] > w:
q.append(-1)
else:
q.append(truck[curTruck])
if truck[curTruck] != -1:
qSize += truck[curTruck]
curTruck+=1
t += 1
if(qSize == 0): break
print(t)
