7137 : 트럭 다리 통과
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
L 길이의 다리에 N개의 트럭들이 차례대로 통과하려고 합니다.
다리에는 동시에 올라갈 수 있는 최대 무게 W가 정해져 있습니다. 다리에 올라간 트럭들의 총 무게가 W 이하여야만 추가 트럭이 올라올 수 있습니다.
각 트럭이 다리를 건너는 데는 L초가 소요된다고 할 때, 모든 트럭이 다리를 건너가기 위해 필요한 최소 총 시간(초)을 계산하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
다리에는 동시에 올라갈 수 있는 최대 무게 W가 정해져 있습니다. 다리에 올라간 트럭들의 총 무게가 W 이하여야만 추가 트럭이 올라올 수 있습니다.
각 트럭이 다리를 건너는 데는 L초가 소요된다고 할 때, 모든 트럭이 다리를 건너가기 위해 필요한 최소 총 시간(초)을 계산하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 트럭의 개수 N, 다리의 길이 L, 다리의 최대 하중 W가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 10,000, 1 ≤ L ≤ 100, 1 ≤ W ≤ 10,000)
둘째 줄에 각 트럭의 무게 N개가 공백으로 구분되어 주어집니다. 각 트럭 무게는 W 이하입니다.
둘째 줄에 각 트럭의 무게 N개가 공백으로 구분되어 주어집니다. 각 트럭 무게는 W 이하입니다.
출력 설명
모든 트럭이 다리를 완전히 통과하는 최소 시간을 초 단위로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5 10
7 4 5 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
17도움
큐(Queue) 자료구조를 다리의 길이 L만큼 0으로 채워둔 상태로 구현하고, 매초마다 큐의 가장 앞 원소를 빼서 무게 합에서 제외하고, 대기 트럭이 추가 진입 가능하면 진입시키며 불가능하면 0을 추가하여 시뮬레이션합니다.