13335 트럭

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

13335번: 트럭

간단한 문제이지만 논리를 헷갈려서 헤맸던 문제였다. 입력의 크기가 작기 때문에 다리를 다 빠져나가는 시간을 바로 계산하지 않고, 1초 단위로 계산하여도 100만으로 시간이 충분하다. 따라서 time이라는 변수를 증가시켜 계산하도록 하고, 무게 제한을 구현하기 위해 deque를 사용하였다. 이후 트럭의 대기 큐에서 하나씩 빼내어 넣게 되는데, 이 때 주의할 점은 트럭이 다리를 다 빠져나갔을 때 다른 트럭이 동시에 들어올 수 있다는 점에 유의한다.

import java.io.*;
import java.util.*;
public class Main {
  static int N, W, L;
  static Queue<Integer> q = new ArrayDeque<>();
  public static void main(String[] args) throws Exception {
    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());
    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < N; i++){
      q.add(Integer.parseInt(st.nextToken()));
    }
    int time = 0;
    Queue<Integer> wait = new ArrayDeque<>();
    Deque<Integer> bridge = new ArrayDeque<>();
    wait.add(1);
    bridge.addLast(q.poll());
    while(!q.isEmpty() || !wait.isEmpty()){
      ++time;
      //트럭이 다 빠져나갔을 때
      if(time >= wait.peek() + W){
        wait.poll();
        bridge.pollFirst();
      }
      //트럭은 동시에 들어올 수 있기 때문에 이 조건이 아래에 있어야 한다.
      //무게 제한에 걸리지 않고 트럭이 더 들어갈 수 있다면
      if(!q.isEmpty()){
        if(bridge.stream().reduce(0, Integer::sum) + q.peek() <= L){
          wait.add(time);
          bridge.addLast(q.poll());
        }
      }
    }
    System.out.println(time);
  }
}