[백준 13335] 트럭 (Python)

문제

 

내 코드

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

truck = list(map(int, input().split()))

min_time = 1
idx = 1
bridge = [0 for _ in range(w-1)]
bridge.append(truck[0])

while(sum(bridge)):
    bridge.pop(0)
    if idx < n and sum(bridge) + truck[idx] <= l :
        bridge.append(truck[idx])
        idx += 1
    else: 
        bridge.append(0)
    min_time += 1

print(min_time)

처음엔 단순히 트럭이 다음 트럭과 합하면 다리의 최대하중을 넘어 1대만 지나갈때 -> 다리길이, 여러대여도 최대하중을 안넘어 여러대가 지나갈때 -> 다리길이 + 트럭 갯수 -1 로 계산 했다가 틀렸다..

 

내가 간과했던 점은 여러대가 지나갈때 그중 몇개가 왼쪽에 도착하면 오른쪽 트럭이 다리위로 올라가도 최대하중을 넘지않는 경우가 있기 때문에 꼭 출발한 트럭들이 다 지나가지 않더라도 중간에 새로운 트럭이 다리위로 올라갈 수 있다는 것이다.

 

그래서 bridge 리스트를 만들었고 pop(0)과 append를 이용하여 1초가 지날때 마다 pop(0)을 해주고 오른쪽 트럭 + 다리 위 트럭의 무게가 최대 하중 이하이면 append(truck[idx]) (다리에 오른쪽 트럭 올려준다는 의미) 를 해주고 그렇지 않다면 append(0)을 해주었습니다.

그리고 while문을 이용해 bridge에 아무것도 없을 때 까지 반복하였습니다.

 

이렇게 bridge 리스트를 만들어 다리 위 트럭 무게를 계산하여 모든 트럭이 다 지나가지 않았더라도 최대하중을 넘지 않는 다면 오른쪽의 새로운 트럭이 다리로 올라갈 수 있도록 하였습니다.

 

 

틀린 코드

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

truck = list(map(int, input().split()))

min_time = 0
idx = 0

while(idx < n):
    weight = truck[idx]
    truck_num = 1
    # 트럭 여러 대가 지나가는 경우
    if idx != n-1 and weight + truck[idx + 1] < l:
        for i in range(idx+1, n):
            if weight + truck[i] <= l:
                weight += truck[i]
                idx = i
                truck_num += 1
            else:
                break
        min_time += w + truck_num - 1
    # 트럭 한 대만 지나가는 경우
    else: 
        min_time += w
    idx += 1

 

 

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

13335번: 트럭