[Algorithm][BOJ 13335] 트럭 - python

문제

 

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

13335번: 트럭

트럭 갯수 : n, 다리의 길이 : w, 다리의 최대 하중 : L
- w대의 트럭만 동시에 올라갈 수 있다.
- 단위 시간에 하나의 단위 길이만큼 이동한다고 가정
- 다리 위에 올라가있는 트럭의 무게 합 <= L

- 이 때 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램 작성해라.

 

풀이

 

풀이 - 큐

- 건너지않은 트럭이 담긴 nList와 다리 위에 있는 트럭이 담긴 bridge => deque 사용- nList에서 트럭을 뺄 때와 빼지 않을 때를 고려한다.

 

반복문 사용

- 공통적으로 시간+1, bridge에서 하나를 뺀다.(bridge는 처음에 w*0으로 초기화)

- nList가 비워있지 않을 때, 다리 위에 올라가있는 트럭의 무게 합이 L보다 작거나 같을 때만 nList에서 트럭을 빼고 bridge에 더한다. 

- bridge가 다 비워졌을 때 반복문을 종료한다.

 

 

Python 코드

 

import sys
from collections import deque

input = sys.stdin.readline

# n : 트럭 갯수, w : 다리의 길이, L : 다리의 최대 하중
[n, w, L] = list(map(int, input().split(' ')))

nList = deque(map(int, input().split(' '))) # 건너지 못한 트럭

answer = 0

bridge = deque([0]*w) # 다리 위에 있는 트럭
idx = 0

summary = 0

while True :
    answer+=1
    bTruck = bridge.popleft()
    summary-=bTruck
    if len(nList) !=0 :
        if summary+nList[0] <= L :
            nTruck = nList.popleft()
            bridge.append(nTruck)
            summary+=nTruck

        else :
            bridge.append(0)
        
    if not bridge :
        break
        
print(answer)

 

 

후기 및 보완할 점

 

19~21줄을 밖으로 빼는 것, 그리고 조건문에서 헤맨 것 같다.좀 더 흐름을 익히는 게 필요한 듯하다...