[백준][13335번] 트럭

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

 

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

 

 

 

내 생각

문제 요약

1. 주어진 순서대로 트럭이 다리를 건널 때 모든 트럭이 다리를 건너는 최단 시간 구하라.

2. 트럭은 시간마다 한 단위의 길이만큼만 이동할 수 있다.

3. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 최대하중을 초과할 수 없다.

 

 

Input)

4 2 10

7 4 5 6

Output)

8

 

 

간단하게 말해서 트럭이 지날 때 최대하중 l을 초과하면 안된다. 트럭이 지나가는 배열을 만들고, 지나가고 있으면 배열에 넣고, 지나갔으면 배열에서 뺀다 !(다리 자체를 배열로 만든다고 보면 될듯하다.) 아무튼 이걸 쉽게 하려면 큐를 이용하면 됨!

그러면서 횟수를 count한다. 

 

1. 

q : 7 4 5 6

b : 0 0

q가 있고(7 4 5 6) sum(b) + q[0] 이 l(10)보다 작다면(7), 다리를 지나가고 있으니 b에 q를 빼서 넣는다. 

2. 

q : 4 5 6

b : 0 7

q가 있고(4 5 6) sum(b) + q[0] 이 l(10)보다 크다면(11), 다리를 지나가지 못하니 0을 추가해준다. (지나가고 있는걸 표현)

3.

q : 4 5 6

b : 7 0

 

이걸 b에 있는 동안은 반복한다 !!!

 

 

 

내 코드

import sys

n, w, l = map(int, input().split())  # 트럭의 수, 다리의 길이, 최대하중
q = list(map(int, input().split()))  # 각 트럭의 무게

b = [0] * w  # 다리
time = 0

# 다리가 비어있을 때까지 반복
while b:
    time += 1
    b.pop(0)  # 다리 첫번째 요소 pop하여 트럭 이동

    # 트럭이 아직 남아있을 때
    if q:
        # 다리에 새로운 트럭이 올라갈 수 있는지 확인
        if sum(b) + q[0] <= l:  # 다리 위의 트럭 무게와 새 트럭의 무게 합이 최대하중 이하인지 확인
            b.append(q.pop(0))  # 다리에 새로운 트럭 추가
        else:
            b.append(0)  # 다리에 새로운 트럭을 추가하지 않고, 무게가 0인 트럭을 추가하여 위치를 이동

print(time)