백준 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

4 2 10
7 4 5 6

예제 출력1

8

예제 입력2

1 100 100
10

예제 출력2

101

예제 입력3

10 100 100
10 10 10 10 10 10 10 10 10 10

예제 출력3

110

시도

• 다리를 올라가기 전 트럭에 대한 Queue인 queue와 다리에 올라가 있는 트럭에 대한 Queue인 bridgeQueue 두 개를 사용하는 방식으로 접근 함
• bridgeQueue의 크기가 w보다 작고, 다리위에 올라가 있는 트럭의 무게와 이제 올라올 예정인 트럭의 무게(queue.peek())의 합이 L 보다 작으면 queue에서 poll() 하고 bridgeQueue에 offer 함
• 이런식으로 조건문 여러개의 분기를 이용해서 구현하였더니, 조건문에 해당하지 않을 경우에도 다리 위의 트럭을 이동시켜야하는 부분에서 문제가 생겼다.

풀이

• bridgeQueue를 w의 크기만큼 0으로 채워 초기화를 시켜 놓은 상태에서 조건에 해당할 경우 offer를 시켜주도록 하였다.
• 그리고 무조건 한 단위 시간마다 poll을 시켜주고, 이 반복문은 bridgeQueue가 비어 있을때까지 반복한다.
• 만약 다리에 올라갈 수 있는 조건이 되면 queue에서 poll을 해와서 bridgeQueue에 offer 해주고, 그렇지 않다면 bridgeQueue에 0을 offer 해주어 한 칸씩 인덱스가 이동되도록 한다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        Queue<Integer> truck = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            truck.offer(Integer.parseInt(st.nextToken()));
        }

        int time = 0;
        int bridgeWeight = 0;
        Queue<Integer> bridgeQueue = new LinkedList<>();
        for (int i = 0; i < W; i++) {
            bridgeQueue.add(0);
        }

        while (!bridgeQueue.isEmpty()) {
            time++;
            bridgeWeight -= bridgeQueue.poll();
            if (!truck.isEmpty()) {
                if (truck.peek() + bridgeWeight <= L) {
                    bridgeWeight += truck.peek();
                    bridgeQueue.offer(truck.poll());
                } else {
                    bridgeQueue.offer(0);
                }
            }
        }
        System.out.println(time);
    }
}