BOJ 13335 트럭

문제

 

코드

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

if __name__ == "__main__":
    n, bridge, max_bridge_weight = map(int, input().split())
    weight = list(map(int, input().split()))
    
    q = deque(weight)
    on_bridge = deque([0] * bridge)
    bridge_weight = 0 
    cnt = 0

    while q or bridge_weight > 0:
        # 매 초마다 맨 앞칸이 다리에서 나감
        bridge_weight -= on_bridge.popleft()
        
        # 새트럭 오는 것 확인
        if q and bridge_weight + q[0] <= max_bridge_weight:
            truck = q.popleft()
            on_bridge.append(truck)
            bridge_weight += truck
        else:
            on_bridge.append(0)
        
        cnt += 1
        
    print(cnt)

 

이 문제는 시간이 1초씩 흐르면서 다리 위 상태가 변하는 문제이다.

트럭이 오른쪽에서 들어가서 왼쪽 다리 출구로 나오므로 deque를 사용하면 된다.

 

 

핵심은 다음 코드이다.

on_bridge = deque([0] * bridge)

 

예를 들어 다리 길이가 2면 아래와 같다.

on_bridge = deque([0, 0])

 

이건 실제로 이렇게 된다.

[다리 앞쪽, 다리 뒤쪽]
[0, 0]

 

트럭이 다리에 올라오면 맨 뒤에 들어가게 되고, 시간이 흐르면 왼쪽으로 한 칸씩 이동해서 맨 앞에서 빠져나간다.

예를 들어 입력이 이것일때,

4 2 10
7 4 5 6

 

이는:

트럭 4대
다리 길이 2
최대 하중 10
트럭 무게: 7, 4, 5, 6

 

 

초기상태는:

대기 트럭 q = [7, 4, 5, 6]
다리 상태 on_bridge = [0, 0]
현재 다리 무게 bridge_weight = 0
시간 cnt = 0

 

1초 후

bridge_weight -= on_bridge.popleft()

 

맨 앞 0 이 빠져나간다.

[0, 0] → [0]
bridge_weight = 0

 

 

이제 새 트럭인 7을 다리 위에 올릴 수 있는지 본다.

bridge_weight + q[0] <= max_bridge_weight
0 + 7 <= 10

 

가능하기 때문에 7을 다리 위에 올린다.

q = [4, 5, 6]
on_bridge = [0, 7]
bridge_weight = 7
cnt = 1

 

그러므로 현재 상태는 다음과 같다.

다리: [0, 7]

 

2초 후

다시 맨 앞 칸이 빠져나간다.

[0, 7] → [7]
빠진 값 0
bridge_weight = 7

 

다음 트럭인 4를 올리려고 보니, 7 + 4 = 11 > 10 이므로 올리지 못한다.

따라서 빈 칸인 0을 넣는다.

q = [4, 5, 6]
on_bridge = [7, 0]
bridge_weight = 7
cnt = 2

 

그러므로 현재 상태는 다음과 같다.

다리: [7, 0]

 

3초 후

다시 맨 앞 칸이 빠져나간다.

[7, 0] → [0]
빠진 값 7
bridge_weight = 0

 

이제 7이 완전히 다리를 넘어갔으므로 다음 트럭인 4가 다리에 올라갈 수 있다.

q = [5, 6]
on_bridge = [0, 4]
bridge_weight = 4
cnt = 3

 

4초 후

맨 앞 0이 빠진다.

[0, 4] → [4]
bridge_weight = 4

 

다음 트럭인 5는 현재 트럭인 4와 더했을 때 10이라 최대하중을 넘기지 않는다.

따라서 현재 상태는 다음과 같이 된다.

q = [6]
on_bridge = [4, 5]
bridge_weight = 9
cnt = 4

 

5초 후

맨 앞 4가 빠진다.

[4, 5] → [5]
bridge_weight = 5

 

다음 트럭인 6은 현재 트럭인 5와 더했을 때 11이므로 최대하중을 넘기기 때문에 올라가지 못한다.

따라서 현재 상태는 다음과 같다.

q = [6]
on_bridge = [5, 0]
bridge_weight = 5
cnt = 5

 

6초 후

이제 맨 앞 5가 빠지므로 다음 트럭인 6을 올릴 수 있다.

[5, 0] → [0]
bridge_weight = 0

 

따라서 현재 상태는 다음과 같다.

q = []
on_bridge = [0, 6]
bridge_weight = 6
cnt = 6

 

여기서 대기 트럭인 q는 비었으나, 6은 아직 다리에 있으므로 계속 진행한다.

while q or bridge_weight > 0:

 

7초 후

맨 앞 0이 빠지고 다음과 같이 된다.

[0, 6] → [6]
bridge_weight = 6

 

대기 트럭은 없으므로 빈칸을 추가하여, 상태는 다음과 같이 된다.

on_bridge = [6, 0]
bridge_weight = 6
cnt = 7

 

8초 후

맨 앞 6이 빠지고,

[6, 0] → [0]
bridge_weight = 0

 

대기 트럭이 없으므로 빈칸이 추가된다.

on_bridge = [0, 0]
cnt = 8

 

이제 q도 없고, bridge_weight도 0이므로 반복이 종료되고, 답은 8이 된다.

 

 

코드 전체

while q or bridge_weight > 0:

=> 아직 처리할 트럭이 있거나 다리 위에 트럭이 있으면 계속한다.

 

bridge_weight -= on_bridge.popleft()

=> 1초가 지나서 다리 맨 앞 칸이 빠져나간다.

 

if q and bridge_weight + q[0] <= max_bridge_weight:

=> 대기 중인 다음 트럭을 올려도 다리 하중을 넘지 않는지 확인한다.

 

truck = q.popleft()
on_bridge.append(truck)
bridge_weight += truck

=> 올릴 수 있으면 트럭을 다리 뒤쪽에 넣고, 다리 위 총 무게를 증가시킨다.

 

else:
    on_bridge.append(0)

=> 못 올리면 빈 칸을 넣는다. 시간이 흘렀으므로 다리 길이는 계속 유지해야 하기 때문이다.

 

cnt += 1

=> 1초가 지남을 기록한다.

 

 

on_bridge는 다리 위 트럭 목록이 아니라 다리의 칸 상태라는 것을 유의하면 쉽게 이해가 가능하다.