[BOJ] 13335번 : 트럭 [S1]

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

13335번: 트럭

 

 

 

[문제]

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

[입력]

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

[출력]

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

 

[예제 입력 1]

4 2 10
7 4 5 6

[예제 출력 1]

8

 

[예제 입력 2]

1 100 100
10

[예제 출력 2]

101

 

[예제 입력 3]

10 100 100
10 10 10 10 10 10 10 10 10 10

[예제 출력 3]

110

 

 

[내 풀이]

package SSAFY.BOJ.stack_queue;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/*
    문제 : [S1] 트럭 - 13335번
    결과 : 통과
    성능 요약 : 메모리 14524KB, 시간 136ms
    아이디어 : 큐를 이용해 문제를 풀었습니다.
              큐를 탈출할 조건, 큐에 진입할 조건을 구현하는게 고려해야하는 것도 많고 생각보다 까다로웠습니다.
*/

public class BOJ_13335_트럭 {

    static int n, w, L;
    static int weights, t;
    // 0행 = 트럭의 무게, 1행 = 트럭이 들어온 시간
    static int[][] trucks;
    // 다리에 올라와있는 차 갯수
    static Queue<Integer> q = new ArrayDeque<>();

    static void calTime() {
        // 시간 초기값
        t = 1;
        for (int i = 0; i < n; i++) {
            // 현재 다리의 무게 + i번째 트럭의 무게가 최대하중보다 작은 경우
            if (weights + trucks[i][0] <= L) {
                q.offer(i);
                weights += trucks[i][0];
                // 트럭이 다리에 올라온 시간
                trucks[i][1] = t;
            } else {
                // 그렇지 않은경우 다리에서 트럭이 내려올 때 까지 시간이 지나야 다음 트럭이 올라갈 수 있음
                while (weights + trucks[i][0] > L) {
                    weights -= trucks[q.peek()][0];
                    t = trucks[q.poll()][1] + w;
                }

                // 이제 다리에 올라갈 수 있음
                weights += trucks[i][0];
                q.offer(i);
                trucks[i][1] = t;
            }
            t++;
            // 시간이 지나서 자연스럽게 다리 지나온 트럭 체킹
            while (t > trucks[q.peek()][1] + w) {
                weights -= trucks[q.poll()][0];
            }
        }
    }

    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());
        trucks = new int[n][2];
        w = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

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

        calTime();
        // 맨 마지막 트럭이 다리를 건너오려면 (w-1)의 시간이 필요함.
        System.out.println(t+(w-1));
    }
}

 

 

새벽에 풀어서 그런지 조건을 만족하게끔 코드를 짜는게 생각보다 어려웠다..

풀이가 한시간 반이 넘어가니까 정신이 혼미해지는데 내가 이정도 난이도도 못푼다는게 화가나서 이악물고 풀었다😢