[백준 Java] 13335번 트럭( 데크 (Deque))

 

[Silver I] 트럭 - 13335

문제 링크

성능 요약

메모리: 12844 KB, 시간: 96 ms

분류

자료 구조, 구현, 큐, 시뮬레이션

문제 설명

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 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개의 정수 a₁, a₂, ⋯ , a_n (1 ≤ a_i ≤ 10)가 주어지는데, a_i는 i번째 트럭의 무게를 나타낸다.

출력

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

💡 나의 접근

처음에는 여러 방식으로 접근해보았으나... 자꾸 로직에 오류가 있어서 어떻게 할까하다가 

문제에서 한 보여준 순서 그대로 다리를 데크로 만들어서 앞에서는 도착한 트럭 빼고 뒤에서는 다리를 건널 트럭 넣고

하는 방식으로 했다.

중간중간 트럭과 트럭사이 빈 순서는 어떻게 처리하나 고민했는데 -1로 구분해주었다.

또한 데크에 넣는 값은 트럭의 무게가 아닌 인덱스를 넣어주었고 트럭은 초기화 할때 다리의 길이만큼 마지막에 0을 붙여주었다. 그래야 무게의 영향이 없이 마지막 트럭을 반대편 끝까지 보낼 수 있기 때문이다.

sum변수를 활용해서 현재 트럭위에 있는 트럭의 무게의 총합이 몇인지 확인하였다.

 

 다음 time에 다리를 건널 트럭이 없을때까지 반복

      1. 반대편에 도착하는 트럭이 있다면 그 트럭의 무게를 sum에서 빼기 

      2. 다음에 건너기를 대기하는 트럭의 무게 + 현재 다리 위에 있는 트럭무게 총합 확인

          2-1. 두 합이 다리 최대하중보다 작거나 같다면 

                    sum에 다리에 추가되는 트럭의 무게 더하기

                    데크에 추카

                    다음에 건너기를 대기하는 트럭의 인덱스 번호를 바꿔줌

          2-2. 두 합이 다리 최대하중보다 크다면

                    다리에 트럭을 올릴수 없으므로 -1을 큐에 넣기

 

      시간 증가

위 예제를 간단히 몇단게만 그림으로 그려보자면

 

💡 코드

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

public class Main {
	static int n;
	static int w;
	static int L;
	static int truck[];
	static Deque<Integer> bridge;
	public static void main(String[] args) throws IOException {
		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());
		
		truck = new int[n+w];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			truck[i] = Integer.parseInt(st.nextToken());
		}
		//--------입력
		
		bridge = new LinkedList<>();
		for (int i = 0; i < w; i++) {
			bridge.add(-1);
		}
		
		int time = 0;
		int sum = 0; //현재 다리 위에 있는 트럭의 무게 합
		int nextIdx = 0; //다음순서에 다리로 출발하려는 트럭의 인덱스 번호
		
		/*
		 * 다음에 다리를 건너기를 출발하려는 트럭의 인덱스를 큐에 넣는다
		 * 트럭과 트럭사이는 -1로 표기한다.
		 * 
		 */
		while (nextIdx != truck.length) {
			
			//Out
			//다리를 건너 도착하는 트럭이 있다면 다리에서 out
			int outIdx = bridge.removeFirst();
			if(outIdx != -1) {
				sum -= truck[outIdx];
			}
			
			//In
			//다음 대기하는 트럭이 다리위에 건너도 하중보다 작은지 확인 후 다리 in
			//하중보다 크다면 -1을 다리로 보냄
			if (sum + truck[nextIdx] <= L) {
				sum += truck[nextIdx];
				bridge.addLast(nextIdx);
				nextIdx++;
			}else {
				bridge.addLast(-1);
			}
			
			time++;
		}
		
		System.out.println(time);
		
	}

}