문제링크

풀이1

다리를 길이 w인 큐(Queue)로 보고, 트럭이 다리 위를 한 칸씩 "이동"하며 다리 위 총 무게가 l 이하일 때만 트럭이 올라갈 수 있도록 시뮬레이션한다.

초기 상태는 아무것도 올라오지 않은 상태이므로 큐에 다리길이만큼 0을 넣어준다.
그리고, 통과된 트럭이 총 트럭 수와 같을 때까지 while문을 돌린다.
while문 내에서는 다음과 같은 과정을 따른다.

1. 가장 앞쪽을 다리 밖으로 한칸 이동시킨다. (bridge.poll())
   • 해당 값이 0보다 크면, 트럭이 다리를 통과한 것이니 passedTrucks를 1 증가시킨다.
2. 다리 위 여유 무게 확인
   • 다리 위 남은 무게가 다음 올라올 트럭보다 크거나 같은 경우(다음 트럭이 올라올 수 있는 경우)
     -> 다음 트럭을 다리 위로 이동시킨다. (bridge.offer(nextTruckWeight))
   • 다리 위 남은 무게가 다음 올라올 트럭보다 작은 경우(다음 트럭이 올라올 수 없음)
     -> 트럭이 올라오지 않았으니 빈공간이다. 0을 채워준다.
3. 시간을 증가시킨다.

• 종료 조건: passedTrucks == n이면 모든 트럭이 다리를 완전히 건넜다는 의미

코드1

package BOJ;

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

public class sol13335 {
    static int n, w, l;
    static int[] trucks;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            trucks[i] = Integer.parseInt(st.nextToken());
        }
        Queue<Integer> bridge = new LinkedList<>();
        for (int i = 0; i < w; i++) {   //  다리에 초기 값인 0을 모두 할당
            bridge.offer(0);
        }

        int passedTrucks = 0;
        int time = 0;
        int nextTruck = 0;  //  건널 차례인 트럭 인덱스
        int nextTruckWeight = 0;
        while (true) {
            if (passedTrucks == n) {
                break;
            }
            int passed = bridge.poll();  //  가장 앞에를 다리 밖으로 이동
            if (passed != 0) {  //  다리 밖으로 이동 값(트럭)이 0보다 크면, 트럭이 탈출한 것
                passedTrucks++;
            }

            if (nextTruck < n) {   //  아직 다리에 진입하지 않은 트럭이 존재할 경우
                nextTruckWeight =trucks[nextTruck];
            }

            if (l - weightOnBridge(bridge) >= nextTruckWeight) {   //  다리 위 남은 무게가 다음 트럭보다 크면(다음 트럭이 다리에 올라갈 수 있으면)
                bridge.offer(nextTruckWeight);    //  다음 트럭을 다리 위로 이동
                nextTruck++;
            } else { //  다리 위 남은 무게가 다음 트럭보다 작으면(다음 트럭이 올라올 수 없음)
                bridge.offer(0);
            }
            time++;
        }

        System.out.println(time);
    }

    public static int weightOnBridge(Queue<Integer> bridge) {
        int sum = 0;
        for (int weight : bridge) {
            sum += weight;
        }
        return sum;
    }
}

풀이2

풀이1과 비슷한 개념에 아래 사항을 수정

• 다리 위 무게를 변수로 두어 불필요한 계산을 제거하였다.
• 마지막 트럭이 다리 위에 올라기만 하면, 그 시점에서 마지막 트럭이 다리를 완전히 건너는데 걸리는 시간만 더해주면 된다.

코드2

package BOJ;

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

public class sol13335 {
    static int n, w, l;
    static int[] trucks;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            trucks[i] = Integer.parseInt(st.nextToken());
        }

        Queue<Integer> bridge = new LinkedList<>();
        for (int i = 0; i < w; i++) {
            bridge.offer(0);  // 다리 초기화 (길이만큼 0 채움)
        }

        int time = 0;
        int nextTruck = 0;
        int bridgeWeight = 0;

        while (nextTruck < n) {
            time++;

            // 트럭 한 칸 이동 (맨 앞 나감)
            int passed = bridge.poll();
            bridgeWeight -= passed;

            int nextTruckWeight = trucks[nextTruck];
            if (bridgeWeight + nextTruckWeight <= l) {
                bridge.offer(nextTruckWeight);
                bridgeWeight += nextTruckWeight;
                nextTruck++;
            } else {
                bridge.offer(0);  // 올라가지 못하면 빈 공간
            }
        }

        // 마지막 트럭이 다리를 완전히 건너는 데 필요한 시간 추가
        time += w;

        System.out.println(time);
    }
}