[Baekjoon] #13335 - 트럭

다른 사람들의 풀이를 보고 기억하기 위해 기록함 !!

 

접근 방법

다리에서 w 단위길이를 고려하고 트럭이 하나씩 빠져나가는 상황을 생각해서 자료구조 queue를 채택한다.

다리를 위한 큐에는 단위길이 w 만큼 0을 채우고 시작한다.

<순서>

1. 다리에서 수를 하나 뺀다.

2. 다리에 원소가 w 미만으로 있다면 다음 트럭을 넣을 수 있는지 검사한다.

3-1. 현재 다리의 합과 다음 트럭을 더했을 때가 최대 하중 L보다 작다면 트럭을 넣어주고

3-2. 최대 하중 L을 넘는다면 0을 넣는다.

 

도착한 트럭	다리 위에 있는 트럭	다리를 건너야 할 트럭	시간	전체 무게
[]	[0, 0]	[7, 4, 5, 6]	0	0
[]	[0, 7]	[4, 5, 6]	1	7
[]	[7, 0]	[4, 5, 6]	2	7
[7]	[0, 4]	[5, 6]	3	4
[7]	[4, 5]	[6]	4	9
[7, 4]	[5, 0]	[6]	5	5
[7, 4, 5]	[0, 6]	[]	6	6
[7, 4, 5]	[6]	[]	7	6
[7, 4, 5, 6]	[]	[]	8	0

 

n, w, l = map(int, input().split())
trucks = list(map(int, input().split()))
 
bridge = [0] * w    # w만큼 다리 길이 선언
weight, time = 0, 0    # 현재 다리위의 무게, 시간 선언
 
while True:
    out = bridge.pop(0)    # 방금 다리를 건넌 트럭은 다리에서 제거해야한다.
    weight -= out    # 방금 다리 다리를 건넌 트럭의 무게를 weight에서 빼줘야 다음 트럭이 넘어 올 수 있다.
 
    if trucks:    # 넘어 올 트럭이 남아있을 때 
        if weight + trucks[0] <= l:    # 다리 하중을 견딜 수 있으면
            bridge.append(trucks[0])    # 다리를 건너려는 트럭
            weight += trucks[0]    # weight에 현재 다리를 건너려는 트럭 무게 추가
            trucks.pop(0)  
        else:    # 다리 하중을 견딜 수 없으면
            bridge.append(0)    # 0을 추가하여 다리위에 있는 트럭을 먼저 보낸다.
    time += 1    # 조건과 상관없이 시간은 흘러간다.
 
    if not bridge:    # 다리위에 트럭이 다 지나가면 반복문 종료
        break    
print(time)

import sys
from _collections import deque
input = sys.stdin.readline

N, W, L = map(int, input().split())
trucks = deque(list(map(int, input().split())))

answer = 0
bridge = deque([0 for _ in range(W)])

while trucks: # 트럭에 원소가 모두 사라질 동안 아래의 과정을 반복
    bridge.popleft() # 다리에 맨 앞에 있는 트럭을 제거한다.
    if len(bridge) < W: # 제거했을 때 다리위에 존재하는 원소가 W 미만일 때만 원소를 추가한다.
        if sum(bridge) + trucks[0] <= L: # 원소를 추가할 때는 다리의 원소들과 다음 트럭의 합이 L보다 작다면
            truck = trucks.popleft() # 트럭을 넣고
            bridge.append(truck)
        else: # 아니라면 0을 넣어 다리의 길이를 유지한다.
            bridge.append(0)
    answer += 1 # 위 과정을 반복할 때 마다 시간을 1씩 증가시킨다.
answer += W
print(answer)