[백준] 13335 트럭

문제

---

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

 

 

 

 

풀이

---

문제의 설명에 맞게 구현을 하면 되는 문제였다.

 

여기서 현재 다리위에 있는 트럭을 Queue에 담아서 시간이 되면 제거해 주었다.

시간당 1 씩움직이는데 다리의 길이는 w이기 때문에 w 만큼 후에 트럭을 제거해주면 된다.

 

또한 다리에 있는 트럭을 현재까지의 무게총합에 추가될 트럭의 무게가 L 보다 작거나 같으면 추가해준다.

 

<전체 코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int n, w, L;
	static int[] truck;
	
	static class Truck{
		
		int w;
		int time;
		
		Truck(int w, int time){
			this.w = w;
			this.time = time;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		n = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		
		truck = new int[n];
		
		st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0; i < n ; i++) {
			truck[i] = Integer.parseInt(st.nextToken());
		}
		
		int sec = 1;
		int index = 1;
		int totalWeight = truck[0];
		Queue<Truck> nowTruck = new LinkedList<>();
		nowTruck.add(new Truck(truck[0], w));
		while(!nowTruck.isEmpty()) {
						
			if(nowTruck.peek().time == sec) {
				totalWeight -= nowTruck.poll().w;
			}
			
			if(index < n) {
				if(totalWeight + truck[index] <= L) {
					totalWeight += truck[index];
					nowTruck.add(new Truck(truck[index], sec + w));
					index++;				
				}
			}
			
			sec++;
		}
		
		System.out.println(sec);
	}	
}