[백준 13335번] 파이썬 - 트럭

백준 13335_트럭

시간초과 1초, 메모리제한 512MB

# 조건

• 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다.
• 이 다리를 n 개의 트럭이 건너가려고 한다.
• 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다.
• 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다.
• 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다.
  • 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

입력

• 입력 데이터는 표준입력을 사용한다.
• 입력은 두 줄로 이루어진다.
• 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

# 접근방법

• 다리길이 만큼의 리스트를 만들어준다.
• 이후 while 문을 돌려준다.
  • bridge 리스트를 pop(0)를 해준 후
  • truck[0]와 sum(bridge) 가 최대 하중을 넘지 않는다면,
  • truck.pop(0) 후 bridge 리스트에 넣어준다.
  • 최대 하중을 넘는다면 0을 append 해준다.

시간초과

• while문을 사용하는 건 시간복잡도가 괜찮았지만,
• 매번 슬라이싱을 해주며 시간초과가 발생하였다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  


n, w, L = map(int, input().split())  
truck = [*map(int, input().split())]  

time = 0  
idx = 0  

bridge =[0] * w  
if n == 1:  
    print(w+1)  
else:  
    while idx < n:  
        time += 1  

        bridge[1:] = bridge[:w]  
        bridge[0] = 0  
        if sum(bridge) + truck[idx+1] < L:  
            bridge[0] = truck[idx+1]  
            idx += 1  
        if idx == n-1:  
            break  
    print(time + w +1)

통과 코드

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

bridge = [0] * w
time = 0

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