[백준]-[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. Queue를 이용하였다.
2. 처음에 다리위에 트럭들을 나타내는 Queue에 시간 체크를 위해 먼저 다리의 길이만큼 0으로 채운다.
3. Queue(다리)가 빌 때까지 반복을 한다.
4. 반복하면서 Queue(출발)을 체크하면서 다리 위에 올라갈 수 있는지 체크 후 올라갈 수 있으면 Queue(출발)에서 빼서 Queue(다리)에 넣는다. 올라갈 수 없으면 0으로 채워 넣는다.

🎈코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,W,L;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken()); // 다리의 길이
        L = Integer.parseInt(st.nextToken()); // 버틸 수 있는 무게

        Queue<Integer> start = new LinkedList<>(); // 출발하려는 차들
        Queue<Integer> ing = new LinkedList<>(); // 다리 위에 있는 차들

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            int car = Integer.parseInt(st.nextToken());
            start.add(car);
        }
        for(int i=0; i<W; i++){
            ing.add(0);
        }
        int time=0;
        int sum=0;
        while(!ing.isEmpty()){
            time++;
            sum -= ing.poll(); // 도착한 트럭은 합에서 제거
            if(!start.isEmpty()){ // 출발할 트럭이 있을 때
                if(start.peek()+sum <=L){ // 출발할 트럭이 다리위에 올라갈 수 있을 때 
                    int truck = start.poll();
                    sum += truck;
                    ing.add(truck);
                }else{ // 올라갈 수 없으면 0으로 채운다.
                    ing.add(0);
                }
            }
        }
        System.out.println(time);
    }
}