13335번 트럭

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

13335번: 트럭

 

 

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 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번째 트럭의 무게를 나타낸다.

출력

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

 

---

 

풀이 방법

저는 두 개의 Queue를 이용하여 시뮬레이션 방식으로 답을 구했습니다.

 

step1. truck의 무게들을 담은 trucks(Queue)와 다리의 길이만큼 0으로 초기화된 bridge(Queue)를 생성합니다.

 

step2. bridge 한칸이 밀려난 뒤, bridge 위의 총합 + 첫번째 truck의 무게가 L이하이면, truck이 한대 앞으로 나갑니다.

(time = 1)

 

step2-1. bridge 한칸이 밀려난 뒤, bridge 위의 총합 + 첫번째 truck의 무게가 L이상이면, 무게가 0인 truck이 나갑니다.

(time = 2)

 

step2. bridge 한칸이 밀려난 뒤, bridge 위의 총합 + 첫번째 truck의 무게가 L이하이면, truck이 한대 앞으로 나갑니다.

(time = 3)

 

step2. bridge 한칸이 밀려난 뒤, bridge 위의 총합 + 첫번째 truck의 무게가 L이하이면, truck이 한대 앞으로 나갑니다.

(time = 4)

 

step2-1. bridge 한칸이 밀려난 뒤, bridge 위의 총합 + 첫번째 truck의 무게가 L이상이면, 무게가 0인 truck이 나갑니다.

(time = 5)

 

step2. bridge 한칸이 밀려난 뒤, bridge 위의 총합 + 첫번째 truck의 무게가 L이하이면, truck이 한대 앞으로 나갑니다.

(time = 6)

 

step3. trucks가 비었을때, bridge 위의 총합이 0이 될때까지 bridge위의 truck을 한칸씩 밀어내기 

(time = 7)

 

step3. trucks가 비었을때, bridge 위의 총합이 0이 될때까지 bridge위의 truck을 한칸씩 밀어내기 

(time = 8)

 

step4. 최종적으로 걸린 시간 출력 

 

 => 이와 같은 과정은 다소 시간은 오래 걸릴 수 있지만, 정확한 풀이가 가능합니다. 또한, bridge 위의 트럭의 값을 매번 돌면서 구할 수 없으므로 sum 변수를 이용하여 bridge위에 트럭이 올라가거나 내려갈때 +혹은 -시켜주는 게 편리합니다.

 

구현 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		
		Queue<Integer> trucks = new LinkedList<Integer>();
		st = new StringTokenizer(br.readLine()," ");
		for(int i =0;i<n;i++) {
			trucks.offer(Integer.parseInt(st.nextToken()));
		}
		
		int time = 0;
		Queue<Integer>bridge = new LinkedList<Integer>();
		for(int i =0;i<w;i++) {
			bridge.offer(0);
		}
		int sum = 0;
		
		while(!(trucks.isEmpty()&&sum==0)) {
			time++;
			if(!trucks.isEmpty()) {
				sum-=bridge.poll();
				if((trucks.peek() + sum)>L) {
					bridge.offer(0);
				}else {
					int now = trucks.poll();
					bridge.offer(now);
					sum+=now;
				}
			}else {
				sum-=bridge.poll();
			}	
		}
		bw.write(""+time);
		bw.flush();
		br.close();
		bw.close();
	}
}

 

 

---

 

다른 사람의 코드 분석

방법1. 

=> 차이점 : 사전에 bridge를 길이만큼 초기화 하지 않았다.

https://zoomkoding.github.io/%EB%B0%B1%EC%A4%80/2019/09/24/baekjoon-13335.html

줌코딩의 코딩일기

 

방법 2.  

=> 차이점 : queue대신 deque를 이용하였다.(하지만 사용방식은 queue와 동일)

https://kimmeh1.tistory.com/291

[백준 13335] 트럭