백준 13335 트럭 자바(java)

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

13335번: 트럭

 

풀이 방법

큐를 이용하여 구현한다.

대기 트럭의 큐 , 다리 위 트럭의 큐 총 2개의 큐를 만든다.

다리 위 트럭의 큐는 (트럭의 무게, 트럭의 위치) 를 저장한다.

시간을 1초씩 증가시키면서 매초마다 큐의 상태를 확인하고 갱신하는 데 알고리즘 흐름은 아래와 같다.

 

1. 초기 대기 트럭의 큐에 모든 트럭을 삽입한다.

2. 다리 위 트럭들의 위치를 모두 앞으로 1씩 이동시킨다.

3. 다리 위 맨 앞의 트럭의 위치가 0이 되면 pop 하여 제거한다.

4. 대기 큐의 맨 앞 트럭이 다리를 건널 수 있는지 확인하고 대기 큐에서 pop 하여 다리 큐에 넣는다.

    (다리 위에 트럭이 W개 이상이 되지 않고 최대하중이 L 을 넘지 않아야 한다.)

5. 대기 큐와 다리 큐 모두 트럭이 없을 때까지, 즉 모든 트럭이 다리를 건널 때까지 2~4번의 과정을 반복한다. 

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        int n = Integer.parseInt(lines[0]); // 다리를 건너는 트럭의 수
        int w = Integer.parseInt(lines[1]); // 다리의 길이
        int l = Integer.parseInt(lines[2]); // 다리의 최대하중
        Queue<Integer> readyTrucks = new LinkedList<>(); // 대기 중인 트럭
        Queue<int[]> moveTrucks = new LinkedList<>(); // 다리 위를 건너는 트럭

        lines = br.readLine().split(" ");
        for(int i=0; i<n; i++) {
            readyTrucks.add(Integer.parseInt(lines[i])); // 대기 중인 트럭 큐에 삽입
        }

        int time = 0; // 총 걸린 시간
        int totalWeight = 0; // 다리 위 트럭들의 총 무게 합
        while(!readyTrucks.isEmpty() || !moveTrucks.isEmpty()) { // 모든 트럭이 다 건널 때까지
            // 다리 위 트럭의 위치를 1만큼 앞으로 옮김
            for(int[] truck : moveTrucks) {
                truck[1] -= 1;
            }

            // 맨 앞 트럭이 다리를 다 건너면 제거
            if(!moveTrucks.isEmpty() && moveTrucks.peek()[1] == 0) {
                totalWeight -= moveTrucks.poll()[0];
            }

            // 맨 앞 대기 중인 트럭이 다리를 건널 수 있는 지 최대하중과 다리의 길이 비교
            if(!readyTrucks.isEmpty() && readyTrucks.peek() + totalWeight <= l && moveTrucks.size() < w) {
                int weight = readyTrucks.poll(); // 현재 트럭의 무게
                totalWeight += weight; // 다리 위 트럭의 무게에 추가
                moveTrucks.add(new int[]{weight, w}); // 다리 위 트럭에 삽입
            }
            time++;

        }
        System.out.println(time);
    }
}