[백준] 13335번 - 트럭 java

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

 

난이도 :  S1

Tag : Simulation

풀이 일자 : 2025-03-14

---

문제 탐색하기

n : 다리를 건너는 트럭의 수 (1 <= n <= 1,000)

w : 다리의 길이 (1 <= w <= 100)

L : 다리의 최대 하중 (10 <= L <= 1,000)

a(i) : i번째 트럭의 무게

주어진 조건

1. 트럭의 순서는 바꿀 수 없음
2. 다리 위에는 최대 w대의 트럭만 동시에 올라갈 수 있음
3. 트럭들은 매초마다 1만큼 이동하며, 다리 길이를 지나야 완전히 건넘
4. 다리 위 트럭들의 무게 합이 L을 초과할 수 없음
5. 완전히 올라가지 못한 트럭의 무게는 다리의 하중에 포함되지 않음

모든 트럭이 다리를 건너는 최단 시간을 구하는 프로그램을 작성해야 합니다.

가능한 시간복잡도

이 문제는 완전탐색을 이용한 시뮬레이션 문제로 해결할 수 있습니다.

• 최대 n = 1000 개의 트럭을 다리에 올려야 함
• 각 트럭은 다리 길이 w 만큼 이동하며,
• 최악의 경우 트럭 1000개 × 다리 길이 100 = 100,000번 연산 수행
• 이는 1억(10^8) 연산 이하이므로 충분히 해결 가능합니다.

따라서 시간복잡도 O(nw) (최대 100,000번 연산)으로 해결 가능합니다.

알고리즘 선택

이 문제는 큐(Queue)를 활용한 시뮬레이션 방식으로 해결할 수 있습니다.

• 트럭이 순서대로 다리에 올라가야 하므로 FIFO(선입선출) 구조인 큐(Queue)를 활용하는 것이 적절합니다.
• 각 트럭이 다리에서 이동하는 과정을 관리해야 하므로, 다리 위에 있는 트럭을 큐를 이용하여 관리하면 됩니다.
• 큐에 트럭의 무게와 다리에 머무른 시간을 저장하고 매 초 갱신하여 직접 시뮬레이션 해볼 수 있습니다.

---

코드 설계하기

 

• 트럭 정보를 입력받아 배열에 저장
• 큐(Queue<int[]>)를 사용하여 다리 위 트럭을 관리
  • 큐에는 {트럭 무게, 다리 위에서의 위치} 정보를 저장
• 트럭이 다리를 건너는 과정을 시뮬레이션
  1. 현재 다리 위 트럭 이동
  2. 다리에서 나갈 트럭 확인 후 제거
  3. 새로운 트럭이 올라갈 수 있는지 확인 후 추가
  4. 모든 트럭이 다리를 건널 때까지 반복
• 최종적으로 걸린 시간 출력

 

회차 별 수정 사항

1회차 : 종료 조건을 반복문의 맨 위에 배치

// 다리에 아무것도 없고, 모든 트럭이 다리를 건넜다면 종료
if (bridge.isEmpty() && index >= n) break;

 

하지만 이 방식은 트럭이 마지막으로 다리를 건너는 순간을 정확히 반영하지 못하는 문제를 발생시킴

• 트럭이 다리에서 완전히 빠져나간 즉시 종료되므로, 마지막 트럭이 다리를 다 건너는 데 걸리는 시간(w초)이 반영되지 않음
• 결과적으로, 출력되는 시간이 실제보다 더 작아지는 오차 발생

그래서 종료 조건을 맨 마지막에 배치하도록 수정했다.

---

정답코드

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

class Main {
    public static void main(String[] args) throws Exception {
        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());

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

        //트럭의 무게, 트럭이 다리에 머무른 시간을 저장
        Queue<int[]> bridge = new LinkedList<>();
        int time = 0;
        int currWeight = 0;
        int index = 0;
        
        while(true){
            time++;
            
            //트럭이 다 지나갔을 경우
            if(!bridge.isEmpty() && bridge.peek()[1] == w){
                currWeight -= bridge.poll()[0];
            }

            //다리에 트럭을 올릴 수 있는지 확인
            if(index < n && (currWeight + truck[index]) <= l && bridge.size() < w){
                bridge.add(new int[]{truck[index], 0}); //처음은 다리 밖에 있으므로 0
                currWeight += truck[index];
                index++;
            }

            //트럭을 한칸씩 앞으로 이동 (트럭이 다리에 머무른 시간으로 판단)
            for(int[] b : bridge) b[1]++;

            //다리에 아무것도 없고, 모든 트럭을 다 보냈을 경우
            if(bridge.isEmpty() && index >= n) break;
        }
        System.out.println(time);
    }
}