[백준][Java] 13335번 : 트럭

[문제 링크]

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

---

문제 설명

길이가 w, 최대하중 L인 다리를 n개의 트럭이 순서대로 건너간다.

동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 L보다 작거나 같아야 한다.

모든 트럭이 다리를 건너는 최단시간을 구한다.

 

 

 

 

 

 

문제 풀이

문제에 주어진 그대로 구현하는 구현 문제

• idx : 현재 트럭의 번호
• onBridgeW 리스트: 다리 위에 올라가 있는 트럭들 무게의 합
• onBrdigeIdx : 다리 위에 올라가 있는 트럭들의 번호를 담고 있는 리스트
• distance 배열 : 각 트럭마다 다리 위를 이동한 거리를 계산한 배열
• move() : 다리 위에 올라가 있는 트럭들이 이동한 거리를 1씩 증가하는 메서드

idx번 트럭의 무게 + onBridgeW 한 값이

• L보다 작거나 같은 경우 : onBridgeW에 idx 트럭의 무게 추가, onBridgeIdx에 idx 추가, move 메서드  실행
• L보다 큰 경우 : move 메서드 실행

if (onBridgeW + truck[idx] <= l) {  //l보다 작거나 같은 경우
    onBridgeW += truck[idx];
    onBridgeIdx.add(idx);
    move();

    idx++;
} else {    //l보다 큰 경우
    move();
}

 

onBridgeIdx 리스트에서 0번째 원소가 다리의 맨 앞에 위치한 트럭의 번호이다.

이 트럭이 이동한 거리가 w일 경우, 현재 다리의 마지막 칸에 위치해 있어서 다리를 모두 건넌 것이다.

따라서 onBridgeIdx 리스트에서 해당 트럭의 번호를 삭제, onBridgeW에서 해당 트럭의 무게를 뺀다.

int frontTdx = onBridgeIdx.get(0); //다리의 맨 앞에 있는 트럭번호

if (distance[frontTdx] == w) {  //해당 트럭이 다리를 모두 건넌 경우
    onBridgeIdx.remove(0);
    onBridgeW -= truck[frontTdx];
}

 

idx가 n인 경우 while문을 종료하고, 마지막 트럭이 현재 위치에서 다리를 완전히 건너오는 데 걸리는 시간을 따로 더해준다.

result += w - distance[n-1] + 1;//마지막 트럭이 건너오는 시간까지 더한다.

 

예제 1에 위의 풀이 방법을 적용해보면 아래와 같다.

 

 

전체코드

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

public class Main {

    static int[] distance;
    static ArrayList<Integer> onBridgeIdx = new ArrayList<>(); //다리 위 트럭들의 번호
    static int onBridgeW = 0;  //다리 위 트럭들의 무게 합

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();   //트럭의 수
        int w = sc.nextInt();   //다리의 길이
        int l = sc.nextInt();   //다리의 최대하중

        int[] truck = new int[n];
        distance = new int[n];    //각 트럭이 다리를 모두 건넜는지 길이를 나타내는 배열
        for (int i = 0; i < n; i++) {
            truck[i] = sc.nextInt();
        }

        int result = 0; //최단시간
        int idx = 0;    //트럭 번호

        while(true) {
            //모든 트럭이 다 건넌 경우 종료
            if (idx == n) {
                break;
            }

            if (onBridgeW + truck[idx] <= l) {  //l보다 작거나 같으면 idx번 트럭도 다리로 이동
                onBridgeW += truck[idx];
                onBridgeIdx.add(idx);
                move();

                idx++;
            } else {    //l보다 크면 다리 위에 있는 트럭트면 한 칸씩 이동
                move();
            }
            result++;   //이동시간 증가

            int frontTdx = onBridgeIdx.get(0); //다리의 맨 앞에 있는 트럭번호
            if (distance[frontTdx] == w) {  //해당 트럭이 다리를 모두 건넌 경우
                onBridgeIdx.remove(0);
                onBridgeW -= truck[frontTdx];
            }

        }
        result += w - distance[n-1] + 1;//마지막 트럭이 건너오는 시간까지 더한다.
        System.out.println(result);
    }

    public static void move() {
        for (int i = 0; i < onBridgeIdx.size(); i++) {
            distance[onBridgeIdx.get(i)]++;
        }
    }
}

 

 

 

 

 

 

 

다른 풀이

2개의 Queue 사용

• 트럭들의 무게를 담고 있는 큐 truck
• 현재 다리 위에 올라와 있는 트럭들의 위치와 무게를 담고 있는 큐 bridge
  → 처음에는 어떠한 트럭도 존재하지 않기 때문에 큐에 w개의 0을 삽입

bridge 큐가 빌 때까지 아래와 과정을 반복한다.

• bridge 큐에서 값 하나를 빼고, onBridgeW에서 그 값을 뺀다.
  → 다리 맨 앞 쪽에 위치한 트럭 한 대를 다리에서 내려주는 과정(해당 위치에 트럭이 없을 경우 0)
• truck 큐의 맨 앞에 값 +  onBridgeW 한 값이
  • L보다 작거나 같을 경우 : 해당 트럭의 무게를 truck 큐에서 삭제, bridge 큐에 추가, onBridgeW에 추가
  • L보다 클 경우 : bridge 큐에 0 삽입(다리 위에 있는 트럭들만 한 칸 씩 이동)

 

전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();   //트럭의 수
        int w = sc.nextInt();   //다리의 길이
        int l = sc.nextInt();   //다리의 최대하중

        Queue<Integer> truck = new LinkedList<>();
        Queue<Integer> bridge = new LinkedList<>();

        //truck 큐에 트럭의 무게 삽입
        for (int i = 0; i < n; i++) {
            truck.add(sc.nextInt());
        }

        //bridge 큐에 w개 만큼 0 삽입 - 현재 다리에 올라와 있는 트럭의 위치
        for (int i = 0; i < w; i++) {
            bridge.add(0);
        }


        int result = 0; //최단시간
        int onBridgeW = 0;  //다리에 올라와 있는 트럭들 무게의 합

        //다리에 아무것도 존재하지 않을 때까지 수행
        while (!bridge.isEmpty()) {
            result++;

            onBridgeW -= bridge.poll(); //맨 앞의 트럭부터 한 대씩 다리에서 내려온다.
            if(!truck.isEmpty()) {
                if (onBridgeW + truck.peek() <= l) {    //최대하중과 같거나 작을 경우
                    onBridgeW += truck.peek();
                    bridge.add(truck.poll());   //다리에 트럭 올라감
                } else {    //최대하중보다 클 경우
                    bridge.add(0);  //bridge 큐에 0 삽입(트럭이 앞으로 한 칸씩 이동)
                }
            }
        }
        System.out.println(result);
    }
}

 

 

처음에 트럭들의 무게를 큐에 넣어서 푸는 방식도 고민했었는데,

'각 트럭마다 이동한 거리를 따로 계산(위에서 move 배열)해서 다리를 모두 건넜는지 확인해야 한다' 는 것에만 집중하다보니 bridge 큐를 사용할 생각을 하지 못했다.