백준 13335번: 트럭[JAVA]

https://www.acmicpc.net/problem/13335

13335번: 트럭

 

[정답 코드]

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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<>();
        Queue<Integer> bridge = new LinkedList<>();
        int count = 0;
        int bridgeWeight = 0;
        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) {
            truck.add(Integer.parseInt(st.nextToken())); // 트럭의 무게를 큐에 담음
        }

        for (int i = 0; i < w; i++) {
            bridge.add(0); // 현재 다리에 올라와있는 트럭의 무게
        }

        while (!bridge.isEmpty()) { // 현재 다리에 올라와 있는 트럭이 존재하지 않을 때 까지
            count++; // 로직이 진행될 때 마다 시간이 1씩 증가
            bridgeWeight-=bridge.poll(); // 다리에 올라와있는 트럭이 한대 씩 다리에서 내려옴 , queue.poll() : 큐의 맨 앞의 값 추출
            if (!truck.isEmpty()) { // 큐에 담긴 트럭이 존재하지 않을 때 까지
                if (truck.peek() + bridgeWeight <= L) { // 트럭큐에 담긴 맨앞의 값과 현재 다리위에 올라와있는 트럭의 무게의 합이 L 보다 낮을때 , queue.peek() : 큐의 맨 앞의 값 확인
                    bridgeWeight += truck.peek();
                    bridge.add(truck.poll()); // 다리에 한 대 씩 올라감
                } else {
                    bridge.add(0); // 트럭큐에 트럭이 존재하지만 다리의 최대하중 때문에 다리로 못올라갈 경우 truck.poll()은 하지 않는다.
                }
            }
        }
        System.out.println(count);

    }
}

 

[설명]

이 문제는 큐를 활용하면 쉽게 풀 수 있다. 먼저 다리위에 트럭이 몇개가 존재하는지를 담는 큐 bridge 를 하나 만들고, 다리를 건너기 전의 트럭을 담는 truck 큐를 하나 만들어준다.

bridge 큐가 빌때까지 반복한다. 반복문이 한번 반복될때마다 트럭이 다리위에서 한칸씩 전진하는 구조이다. 

한칸 전진할 때마다 truck 큐를 확인하며 truck 큐를 하나 꺼내 다리위에 올라갔을 때 최대하중을 넘는지 안넘는지 체크하고 넘지않는다면 bridge 큐에 넣고 넘는다면 bridge에 0을 집어 넣는다.