13335 트럭(S1)

문제 url : https://www.acmicpc.net/problem/13335

문제 내에 여러 조건이 있지만, 중요 단서 몇 개만 제대로 파악하고 확인할 수 있으면 된다. 아래와 같이 정리해볼 수 있다.

문제를 풀면서 헷갈린 조건들은 굵게 표시해보았다.

* n 개의 트럭이 다리를 건넌다. (순서는 바꿀 수 없다.)

* 다리 위에는 w대의 트럭만 동시에 올라갈 수 있으며, 다리를 건너는 시간 또한 각 트럭당 w의 시간이 걸린다.

* 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다.

* 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다

 

내가 작성한 코드는 아래와 같다.

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

public class Main {
    static int[] trucks;
    static int n,w,l;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n : 트럭 개수
        // w : 다리 길이
        // L : 최대 하중
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        trucks = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
            trucks[i] = Integer.parseInt(st.nextToken());
        }

        solution();
    }

    static void solution() {
        Queue<Integer> queue = new LinkedList<>();
        int curWeight = 0; // 현재 다리 위의 무게
        int time = 0;

        for(int i=1; i<=n; i++) {
            int truck = trucks[i];

            while(true) {
                // 트럭 없는 경우
                if(queue.isEmpty()) {
                    queue.add(truck);
                    curWeight += truck;
                    time++;
                    System.out.println(i + "번쨰 트럭(" + trucks[i] + ")이 비어있는 Queue에 추가되었습니다. 현재 다리 무게 : " + curWeight + ", 현재 시각: " + time);
                    break;
                }

                // 트럭 가득 찬 경우
                else if (queue.size() == w) {
                    curWeight -= queue.poll();
                    System.out.println(i + "번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : " + curWeight);
                }

                // 트럭 추가할 수 있는 경우
                else {
                    if(curWeight + truck <= l) {
                        queue.add(truck);
                        curWeight += truck;
                        time++;
                        System.out.println(i + "번쨰 트럭(" + trucks[i] + ")이 Queue에 추가되었습니다. 현재 다리 무게 : " + curWeight + ", 현재 시각: " + time);
                        break;
                    } else {
                        // 트럭이 한 칸씩 움직임
                        queue.add(0);
                        time++;
                        System.out.println(i + "번쨰에서 트럭이 한 칸 움직입니다. 이때 시간 : " + time);
                    }
                }
            }
        }

        time += w;
        System.out.println(time);
    }
}

진행과정 설명을 위해 각 단계에 출력 코드를 넣어보았다.

실행 결과는 아래와 같이 나온다.

4 2 10
7 4 5 6
1번쨰 트럭(7)이 비어있는 Queue에 추가되었습니다. 현재 다리 무게 : 7, 현재 시각: 1
2번쨰에서 트럭이 한 칸 움직입니다. 이때 시간 : 2
2번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 0
2번쨰 트럭(4)이 Queue에 추가되었습니다. 현재 다리 무게 : 4, 현재 시각: 3
3번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 4
3번쨰 트럭(5)이 Queue에 추가되었습니다. 현재 다리 무게 : 9, 현재 시각: 4
4번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 5
4번쨰에서 트럭이 한 칸 움직입니다. 이때 시간 : 5
4번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 0
4번쨰 트럭(6)이 Queue에 추가되었습니다. 현재 다리 무게 : 6, 현재 시각: 6
8

 Queue에는 현재 다리위에 있는 트럭을 의미한다. 이때, 0을 추가하는 이유가 있다. 이유가 뭘까?

Queue에서 나온 트럭의 무게를 이용해 현재 다리위의 무게를 계산한다. 트럭은 다리를 건널 때, 매 초마다 한 칸씩 이동하게 되는데, 만약 다리 위에 있는 트럭이 끝까지 다리를 건너지 못했다면, 다른 트럭이 다리에 올라가길 기다려야 한다. 트럭이 한 칸씩 이동하는 동안, 그 자리를 유지하기 위해 큐에 0을 추가하는 것이다. 즉, 0을 추가한다는 것은 트럭이 다리를 한 칸 이동하면서 뒤의 트럭이 기다리고 있다는 것을 의미한다.

 

출력문을 토대로, 직접 그려가며 문제를 풆다 보면 쉽게 이해할 수 있을 것이다.

소요시간 : 1시간 15분