백준 13335 : 트럭 Java

www.acmicpc.net/problem/13335

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	3242	1502	1166	51.073%

---

문제

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

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

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

 

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

---

입력

입력 데이터는 표준 입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

---

출력

출력은 표준 출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

---

제한

---

예제 입력	예제 출력
4 2 10 7 4 5 6	8
1 100 100 10	101
10 100 100 10 10 10 10 10 10 10 10 10 10	110

---

풀이 과정

 

다리와 트럭들을 큐를 이용해서 구현합니다. 다리를 건너기 위해서는 최대 하중이 허락하는 만큼만 가능하기 때문에 해당 과정이 필요하고 한번 움직일 때마다 시간을 카운트해줍니다.

이를 위해 초기 다리의 길이만큼의 큐에 0을 넣어줍니다. 이후 하중을 고려하여 트럭의 무게를 넣어주고 하중이 초과된다면 0을 넣어 시간을 계속 카운트 해 줍니다. 트럭이 모두 다리에 올랐다면 반복문이 종료되고 아직 다리위에 남아있는 트럭이 있다면 계속 진행해서 다리를 빠져나오게 해줍니다.

 

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/*
 * https://www.acmicpc.net/problem/13335
 * 트럭
 * 
 * */
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine()," ");
		
		Queue<Integer> bridge_on = new LinkedList();		//다리위에있는 트럭들
		Queue<Integer> truck_weights = new LinkedList();	//각 트럭들의 무게
		
		int N=Integer.parseInt(st.nextToken());		//다리를 건너는 트럭의 수
		int W=Integer.parseInt(st.nextToken());		//다리의 길이
		int L=Integer.parseInt(st.nextToken());		//다리의 최대 하중
		
		int answer = 0;			//걸린 시간
		int curr_weight = 0;		//다리 위에있는 트럭의 무게
		int bridge_out=0;			//다리를 빠져나오는 트럭
		int truck =0;				//대기하던 트럭의 무게
		int[] arr = new int[N];
		
		st = new StringTokenizer(br.readLine()," ");
		
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			truck_weights.add(arr[i]);
		}
		
		for (int i = 0; i < W; i++) bridge_on.add(0);
		
		while(truck_weights.isEmpty() == false) {	//트럭이 남아있는동안
			answer++;
			bridge_out = bridge_on.poll();		//다리위에 큐에서 나가는 트럭 빼기
			curr_weight -= bridge_out;			//다리 무게 
	
    //다리에 올라가있는 트럭과 대기하고있는 트럭의 무게가 다리최대 하중보다 크다면 0을 추가
			if(curr_weight + truck_weights.peek() > L)	bridge_on.add(0);	
			else {				
				truck = truck_weights.poll();
				bridge_on.add(truck);			//트럭 한대 전진
				curr_weight += truck;			//무게 갱신
			}
		}
		
		while(curr_weight > 0) {			//아직 다리를 건너고있는 트럭 계산
			answer++;
			bridge_out = bridge_on.poll();
			curr_weight -= bridge_out;
		}
		
		System.out.println(answer);
	}
}