[BOJ] 백준 13335 - 트럭 풀이

1. 문제

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

13335번: 트럭

 

 

2. 풀이

시뮬레이션 문제이므로 문제에서 주어지는 시나리오 대로 문제를 해결하면 된다.
문제를 처음에 보고 큐와 비슷하다고 생각했다. 그런데 처음엔 큐를 사용하지 않고 List를 사용하여서 문제를 해결하려 했는데 시간초과가 발생했다. 탐색을 여러 번 해야 하고, 불필요한 반복의 호출이 많아서 발생했다고 추측한다. 시간 초과 발생 후 다시 큐를 이용하여 문제를 해결했다.

* 시간 초과가 발생한 코드

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

class Main {
    static int N;
    static int W;
    static int L;

    static List<Truck> truckList = new ArrayList<>();
    static List<Truck> bridge = new ArrayList<>();

    static int cnt = 0;
    static int idx = 0;
    static int result;

    static class Truck {
        int weight;
        int time;

        public Truck(int weight, int time) {
            this.weight = weight;
            this.time = time;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            Truck truck = new Truck(Integer.parseInt(st.nextToken()), 0);
            truckList.add(truck);
        }

        while (true) {
            if(cnt == N)   {
                break;
            }

            // 시간 증가
            for (int i = 0; i < bridge.size(); i++) {
                if (bridge.get(i).time <= W) {
                    bridge.get(i).time += 1;
                }
            }

            // 다 된건 삭제
            if (!bridge.isEmpty() && bridge.get(0).time == W + 1) {
                bridge.remove(0);
                cnt += 1;
                idx += 1;
            }

            // 로직 : 하나도 못지나가는 경우는 없음
            if (cnt != N && bridge.isEmpty()) {                  // 다리에 한대의 차도 없다면
                truckList.get(idx).time += 1;
                bridge.add(truckList.get(idx));
            }
            else {
                if (cnt != N && idx < N - 1 && isWeight() + truckList.get(idx + 1).weight <= L) {
                    truckList.get(idx + 1).time += 1;
                    bridge.add(truckList.get(idx + 1));
                }
            }
            result += 1;                // 1초가 지남
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();

    }

    static public int isWeight() {
        int weight = 0;

        for (int i = 0; i < bridge.size(); i++) {
            weight += bridge.get(i).weight;
        }
        return weight;
    }
}

우선 다리에 있는 차의 무게를 저장할 큐와 입력 받은 차의 무게를 저장할 큐를 선언 한다. 그 후 각각 초기화를 진행하는데, 다리의 무게를 저장할 큐를 0으로 W만큼 초기화 해준다.

그 후 로직을 수행해주면 되는데, 시간을 의미하는 result를 하나 증가시켜주고 현재 다리에 끝에 있는 차의 무게를 poll()하여 weight에서 빼준다. 그 후 트럭 큐가 비어 있지 않고 (건너야할 트럭이 더 있다면), 다음 트럭의 무게와 weight의 합이 다리에 수용할 수 있는 무게보다 작거나 같다면 weight에 다음 트럭의 무게를 더해주고 다리에 추가를 한다. 
만약 다음 트럭의 무게와 weight의 합이 다리에 수용할 수 있는 무게보다 크다면 다리 큐에 0을 넣어 준다.

마지막으로 최종 걸린 시간인 result를 출력해주면 정답!!

 

3. 소스 코드

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

class Main {
    static Queue<Integer> truckList = new LinkedList<>();
    static Queue<Integer> bridge = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            truckList.add(Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < W; i++) {
            bridge.add(0);
        }

        int result = 0;
        int weight = 0;

        while (!bridge.isEmpty()) {
            // 로직
            result += 1;                // 1초가 지남
            weight -= bridge.poll();

            if (!truckList.isEmpty()) {
                if (truckList.peek() + weight <= L) {
                    weight += truckList.peek();
                    bridge.offer(truckList.poll());
                }
                else {
                    bridge.add(0);
                }
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }
}