알고리즘
백준 13335번 트럭 (JAVA)
박카스마시며코딩
2023. 11. 16. 18:01
https://www.acmicpc.net/problem/13335
13335번: 트럭
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트
www.acmicpc.net
저는 큐를 통해 문제를 해결하였습니다.
큐를 통해 다리에 있는 트럭들을 표현하였고, 큐를 통해 순서대로 꺼내면서 해당 트럭이 끝나는 시간을 추적해가면서 문제를 해결하였습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Test {
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[] weight = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < n ; i++){
weight[i] = Integer.parseInt(st.nextToken());
}
long result = cal(weight,n,w,l);
System.out.println(result);
}
private static long cal(int[] weight, int n, int w, int l) {
int totalWeight = 0;
int time = 0;
Queue<int[]> q = new LinkedList<>();
for(int i = 0 ; i < n ; i++){
boolean flag = false;
while(totalWeight + weight[i] > l){
int[] temp = q.poll();
totalWeight -= temp[0];
if(temp[1] + w > time){
flag = true;
}
time = Math.max(temp[1] + w,time); // 끝나는 시간
}
totalWeight += weight[i];
if(!flag){
time++;
}
q.offer(new int[]{weight[i],time}); // 들어가기 직전 시간
}
while(!q.isEmpty()){
time = Math.max(q.poll()[1] + w,time);
}
return time;
}
}