다리를 지나는 트럭

2026.05.10

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

문제 풀이

나의 코드

소요 시간: 1시간 8분

시간 복잡도: O(bridge_length × n)

---

totalTime, currentWeight, index, arrived.. 등 변수를 많이 사용해서
로직을 짜며 서로 영향을 많이 주고받아 고려해야 할 사항이 많아서 조금 복잡했다.
테스트 케이스를 통해 코드를 한줄 한줄 내려가면서 오류를 찾아가는 과정을 통해
해결할 수 있었다.

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {   
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Deque<int[]> onBridge = new ArrayDeque<>(); // 다리 위에 올라가 있는 트럭
        int totalTime = 1; // 총 걸린 시간
        int currentWeight = 0; // 현재 다리 위에 있는 트럭 무게
        int index = 1;
        int arrived = 0; // 도착한 트럭 수
        int len = truck_weights.length;
        
        if (len == 1) {
            return bridge_length + 1;
        }
        
        boolean fin = false;
        
        onBridge.offer(new int[]{truck_weights[0], 1});
        currentWeight += truck_weights[0];
        
        
        while(true) {
            if (arrived == len) {
                break;
            }
            
            if (!onBridge.isEmpty()) {
                for (int[] arr : onBridge) {
                    arr[1] += 1;
                }
            }
            
            totalTime++;
            int w = truck_weights[index];
            
            if (!onBridge.isEmpty() && onBridge.peek()[1] > bridge_length) { // 다리에서 다 내려왔을 때
                currentWeight -= onBridge.poll()[0]; // 큐에서 삭제
                arrived++;
            }
            
            if (onBridge.size() + 1 > bridge_length || currentWeight + w > weight) {
                // 트럭 한 대가 더 들어았을 때, 다리에 올라갈 수 있는 트럭의 개수를 초과하거나
                // 다리가 견딜 수 있는 무게를 초과하는 경우
                continue;
            }
            else if (!fin) {
                onBridge.offer(new int[]{w, 1}); // 큐에 들어가는 순간 (올라오는 데 1초가 걸리기 때문)
                currentWeight += w;
                index++;
                if (index >= len) {
                    fin = true;
                    index--;
                }
            }
        }
        
        return totalTime;
    }
}

AI 코드

시간 복잡도: O(bridge_length × n)

---

다리를 bridge_length 크기의 큐로 표현하여 0을 빼고 넣는 과정이 핵심 알고리즘임.

7 4 5 6 일 때,
0 0 0 0 → 0 0 0 7 → 0 0 7 0...

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Deque<Integer> bridge = new ArrayDeque<>();
        int time = 0;
        int currentWeight = 0;

        // 다리를 bridge_length 크기의 큐로 표현 (0으로 초기화)
        for (int i = 0; i < bridge_length; i++) {
            bridge.offer(0);
        }

        for (int truck : truck_weights) {
            while (true) {
                if (currentWeight + truck <= weight) {
                    currentWeight -= bridge.poll();
                    bridge.offer(truck);
                    currentWeight += truck;
                    time++;
                    break;
                } else {
                    currentWeight -= bridge.poll();
                    bridge.offer(0);
                    time++;
                }
            }
        }

        return time + bridge_length;
    }
}