[Python] 구현-13335. 트럭(실1) /큐와 시뮬레이션

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

13335번: 트럭

 

>>문제 포인트

- 시간 단위 1씩 판단

- 큐를 통해 bridge와 truck 배열 형성

 

=>본 문제가 어려웠던 이유는 쉽게 풀어볼려고 그리디적으로 접근했기 때문이었다.

=> 하지만, 타임프레임 1초당 판단해야 하는 것들을 목록화하고 구현하는 문제였다.

 

먼저 예시를 통해 시간당 진행상황을 보자

 

하중 : 10

arrived |  bridge(길이 2) |    truck     |  time

[]                      [0,0]             [7,4,5,6]      0

[]                      [0,7]             [4,5,6]         1

[]                      [7,0]             [4,5,6]         2

[7]                    [0,4]             [5,6]            3

[7]                    [4,5]             [6]               4

[7,4]                 [5,0]             [5,6]            5

[7,4,5]              [0,6]             []                 6

[7,4,5]              [6,0]             []                 7

[7,4,5,6]           [0,0]             []                 8

 

=>각 순간마다 판단해야 하는 건 다음과 같다.

1) 먼저 bridge의 맨 왼쪽 항이 다리 끝부분에 도착

2) 트럭을 더 실을 수 있다면 = (현재하중 + truck열 대기 1번 무게) < 다리하중

    => truck 대기 1번 bridge에 넣어주기

3) 트럭을 더 실을 수 없다면 = (현재하중 + truck열 대기 1번 무게) > 다리하중

    => truck 대신 빈공기(0) bridge에 넣어주기

 

#13335
from collections import deque

#n은 트럭의 수 , w은 다리의 길이, L은 다리의 최대하중
n, w, l = map(int, input().split())

truck=deque((map(int, input().split())))
bridge=deque([0]*w)
time=0

while(1):

  #대기트럭/다리 위 트럭이 없을 때
  if len(truck)==0 and sum(bridge)==0:
    break
    
  time+=1
  
  #다리 맨 왼쪽이 반대편에 도착
  bridge.popleft()

  #트럭이 있을 때-> 추가 트럭 건너올 수 있을지 판단
  if truck:
  
    #만약 하중이 버틸 수 있을 때 -> truck건너게하기
    if (sum(bridge)+truck[0])<=l:
      bridge.append(truck.popleft())
  
  #못버틸때 -> 기다림
    else:
      bridge.append(0)

print(time)