문제 탐색하기

입력 자료 정리

1. n은 트럭의 수, w는 다리의 길이, l은 다리의 최대하중을 의미한다
2. 이어서 들어오는 n개의 입력은 각각 트럭의 하중을 의미한다

해결 방법 추론

1. 다리 한칸 한칸의 무게 상태를 관리하고,
   트럭이 모두 건너가서 다리가 빌때까지 시뮬레이션을 돌리면 되겠다고 생각하였다
2. 시뮬레이션 한번당 단위는 시간으로 체크하며,
   각 다리 한칸한칸을 무게 0으로 초기화하여 길이만큼 넣어준다
3. 시뮬레이션마다 다리의 맨 앞을 빼서 다리의 전체 하중의 크기에서 빼주는 방식으로 갱신한다
4. 이 방식으로 갱신한다면, 트럭의 다리 진입 여부도 알 수 있고, 트럭의 위치도 갱신할 수 있다
5. 트럭이 남아있을 때는 현재 트럭의 무게랑 다리 전체 하중의 합산보다 k가 작은지 검토한다
6. 만약 이하라면 전체 하중에 트럭의 무게를 더하고 큐에 트럭을 더해준다
7. 아닐 경우 그냥 0을 더해줘서 다리 한칸한칸의 위치가 계속해서 변하도록 한다
8. 이 시뮬레이션 방법을 선택한다면 문제를 쉽게 해결할 수 있을 것이다.

시간복잡도 계산

1. 최악의 경우는 n의 최대 길이인 1000개의 트럭인 w의 최대길이인 100의 다리에서,
   모두 L의 최대값인 1000보다 커서 각 다리마다 하나의 트럭만이 이동하는 경우다
2. 따라서 n x w가 최대 연산이 되며, 시간복잡도는 O(n x w)가 된다
3. 따라서 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 입력값은 큐를 이용하여 관리한다.
   트럭과 다리 모두 큐를 이용하여 관리하며, 트럭은 입력값을 넣어주고
   다리는 0을 w만큼 넣어준다
2. n,w,k는 모두 변수로 관리하며,
   다리의 전체 하중과 현재 시간은 0으로 초기화하여 변수로 관리한다

시뮬레이션 설계

1. 다리 큐가 비지 않을 동안 매 시뮬레이션마다 시간은 증가시키고,
   다리의 맨 마지막지점인 큐의 맨앞을 빼서 다리 전체 하중에서 빼준다
2. 이어서 트럭 큐가 비어있지 않다면 앞서 추론한 방법대로 진행하여준다

출력값 설계

1. 완성한 현재시간을 관리하는 변수를 출력하면 정답이 된다.

정답코드

(1회차 시도 성공!)

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


public class Main {

    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 k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        Queue<Integer> truck = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            truck.add(Integer.parseInt(st.nextToken()));
        }

        Queue<Integer> bridge = new LinkedList<>();
        int bridgeWeight = 0;
        int nowTime = 0;
        for (int i = 0; i < w; i++) {
            bridge.add(0);
        }

        while(!bridge.isEmpty()){
            nowTime++;
            bridgeWeight -= bridge.poll();
            if(!truck.isEmpty()){
                if(truck.peek() + bridgeWeight <= k){
                    bridgeWeight += truck.peek();
                    bridge.add(truck.poll());
                }else{
                    bridge.add(0);
                }
            }
        }

        bw.write(nowTime + "");

        br.close();
        bw.close();
    }
}

문제 링크

13335번 - 트럭