[백준] 13335: 0 만들기 - JAVA

in Algorithm on 구현

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

풀이

n개의 트럭이 길지 w의 다리를 건너는데 1을 가는데 1의 시간이 소요되고 다리가 견딜 수 있는 무게는 L이다.

다리 위에 L넘게 올라갈 수없다. 먼저 간 트럭이 다리를 벗어날 때까지 기다려야한다.

큐에 다리위에 있는 트럭들을 저장하고 sum에 트럭의 무게를 더해줬다.

큐에 넣을 때 다리를 벗어나는 시간까지 같이 넣어주었다.

시간을 늘리면서 큐의 맨 앞에 있는 트럭이 다리를 벗어날 시간이라면 큐에서 삭제, sum에서 무게를 빼주었다.

sum + 다음에 들어올 트럭의 무게가 L보다 작거나 같으면 큐에 트럭을 넣어주었다.

메모리: 14444KB

시간: 136ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int weight;
        int time;

        public Node(int weight, int time) {
            this.weight = weight;
            this.time = time;
        }
    }

    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());

        int[] truck = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            truck[i] = Integer.parseInt(st.nextToken());
        }

        Queue<Node> queue = new LinkedList<>();
        int time = 1;
        int sum = 0;
        int idx = 1;
        queue.add(new Node(truck[0], w + 1));
        sum += truck[0];
        while (!queue.isEmpty()) {
            time++;
            if (queue.peek().time == time) {
                sum -= queue.peek().weight;
                queue.poll();
            }

            if (idx < n && sum + truck[idx] <= L) {
                queue.add(new Node(truck[idx], time + w));
                sum += truck[idx++];
            }
        }

        System.out.println(time);
    }

}