[Algorithm] 백준 13335 - 구현 / 트럭

백준 실버 ~ 골드 문제를 풀며 정리한 내용입니다.

https://www.acmicpc.net/problem/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번째 트럭의 무게를 나타낸다.

 

출력

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

 

- 예제 입력

4 2 10
7 4 5 6

 

- 예제 출력

8

 

 

📌 풀이

BufferedReader를 이용해 문자열을 입력받고 StringTokenizer를 이용해 해당 문자열을 띄어쓰기를 기준으로 나눠 변수에 저장했다. 각각 다리를 건너는 트럭의 수, 다리의 길이, 다리의 최대하중을 N, W, L 변수에 저장하는데, 이후 문제 구현에 이용하기 위해 Integer.parseIn()를 이용해 형변환 해주었다.

 

다리의 길이인 W만큼 반복하며 queue에 값을 저장한다. 시작 시점에는 다리 위에 아무것도 존재하지 않기 때문에 전부 0으로 저장한다. queue가 비어있지 않다면 계속 반복하며 수행한다. 시간이 지나며 다리 위의 무게와 트럭의 무게를 합친것이 최대하중보다 작은 경우 queue에 해당 트럭을 추가하고 다리 위 무게에 트럭 무게를 더해준다. 이때 트럭의 개수가 1개 줄어들게 되며, 줄어든 수가 0이 되는 순간 더이상 지나갈 트럭이 없는 것이기에 수행이 중단된다. 아직 보내야할 트럭이 남아있다면 트럭 변수에 다음 트럭의 무게를 저장하고 while문을 반복해서 돌게된다.

 

반복문을 한번 돌때마다 단위시간이 1개씩 늘어났다. 반복 수행이 끝난 뒤 time 변수에 저장된 값은 모든 트럭이 다리 위를 올라가보도록 한 상태로, 마지막에 다리 위에 있는 트럭들이 모두 다리를 건너기까지 걸릴 시간(큐의 크기)을 추가해준다.

 

이 문제를 읽고 queue를 이용한 풀이를 바로 생각해내지 못했다. 문제를 어떤 방식으로 풀지 더 빠르게 판단할 수 있도록 해야겠다.

 

 

구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());
        
        Queue<Integer> bridge = new ArrayDeque<Integer>();
        
        for (int i = 0; i < W; i++) {
			bridge.add(0);
		}
        
        st = new StringTokenizer(br.readLine());
        int truck = Integer.parseInt(st.nextToken());
        
        int time = 0;
        int onBridgeWeight = 0;
        
        while (!bridge.isEmpty()) {
            time++;
            
            onBridgeWeight -= bridge.poll();
            if (onBridgeWeight + truck <= L) {
                bridge.add(truck);
                onBridgeWeight += truck;
                
                if (--N == 0) break;
                
                truck = Integer.parseInt(st.nextToken());
            } else {
                bridge.add(0);
            }
        }
        time += bridge.size();
        System.out.println(time);
    }
}