13335 트럭

트럭

13335번: 트럭

문제 : 

트럭이 차례대로 다리에 오를 때, 다리가 버틸 수 있는 하중을 고려하여 트럭이 모두 다리를 건너는 시간을 구하시오. 다리 한 단위를 가는 데 걸리는 시간은 1 단위이다.

 

풀이 : 

시뮬레이션을 통해 시간을 1씩 늘려가면서 구할 수 있다.

각각의 트럭이 다리에 올라가는 시간과 트럭이 다리에서 내려가는 시간( = 올라가는 시간 + 다리의 길이)만을 알 수 있다면, 시뮬레이션 하지 않고 O(n)의 시간에 해결할 수 있다.

트럭이 앞 쪽에서 나가거나 뒤에서 들어오기 때문에 이와 유사한 구조를 가진 queue 자료 구조를 사용하면 편리하다.

 

1. 맨 앞 트럭이 내려갈 시간이 된 경우 -> 맨 앞의 트럭을 다리에서 내리게 한다

2. 현재 보고 있는 트럭이 다리에 올라갈 수 있는 경우 (모든 트럭의 무게 <= l) -> 다리에 올리고, 내려가는 시간을 설정해준다.

 

코드