[Baekjoon] 13335번 : 트럭 (Python, 구현, 시뮬레이션)

[Baekjoon] 13335번 : 트럭 (Python, 구현, 시뮬레이션)

 

목차

 

 

 

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

13335번: 트럭

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 -  코드 길이 564B

 

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

# 다리 위에 올라간 트럭
onB = []
# 현재 시간
time = 0
# 현재의 다리에 올라간 무게 load
load = 0

for idx, a in enumerate(arr):
    if l >= load + arr[idx]:
        time += 1
        onB.append((arr[idx], time))
        load += arr[idx]
    else:
        while l < load + arr[idx]:
            if time == onB[0][1] + w:
                load -= onB[0][0]
                onB.pop(0)
            else:
                time += 1

        onB.append((arr[idx], time))
        load += arr[idx]

time = onB[-1][1] + w
print(time)

 

방법 2 - 메모리 32424KB / 시간 124ms / 코드 길이 367B

 

도착	다리 (w=2)	다리 전 대기 트럭	현재 시간	다리 위 무게
[]	[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	4+5=9
[7,4]	[5,0]	[6]	5	5
[7,4,5]	[0,6]	[]	6	6
[7,4,5]	[6,0]	[]	7	6
[7,4,5,6]	[]	[]	8	0

 

다리에 있는 값들을 하나씩 뽑고 다시 채우는 방식으로 다리 위의 하중을 계산하고

입력받은 트럭들의 queue를 비우게 될 때 나오게 되는 whlie문을 사용한다.

 

이를 통해 시간순으로 진행됨에 따라 하중이 넘지않게 트럭을 모두 운송할 수 있다.

 

from collections import deque

n,w,l = map(int, input().split())
trucks = deque(list(map(int, input().split())))
bridge = deque([0]*w)
time = 0

while trucks:
    bridge.popleft()
    if len(bridge) < w:
        if sum(bridge) + trucks[0] <= l:
            bridge.append(trucks.popleft())
        else:
            bridge.append(0)
    time += 1
time += w
print(time)