BaekJoon

[Baekjoon] 13335번 트럭 (Java) 문제 풀이 [Silver 1]

Tenacity_Dev 2024. 4. 13. 16:43
728x90

문제

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

 

13335번: 트럭

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트

www.acmicpc.net

 

어떻게 풀 것인가?

구현은 너무나도 어렵다. 특정 알고리즘은 외우면 된다지만, 구현은 생각해야할 것들이 너무나도 많다.

이번 문제는 큐를 이용한 구현 문제였다.

 

내가 푼 문제의 코드를 뜯어보자.

다리는 Queue로 선언해 준고 여기에 다리의 길이만큼 0을 넣어준다. 다리의 길이만큼 이동하면서 Queue를 계산하게 된다

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

 

먼저 1초가 지나고 다리에 차가 올라갈 수 있으니, time에 하나를 더해주고,
이렇게 나온 무게는 다리 밖으로 나오므로, bw(다리위무게)에서 내려운 만큼(q.poll())을 빼준다(처음 다리길이까지는 0만빠진다. ) 
그리고 만약 트럭이 남아있다면, if(!truck.isEmpty()) 가장 앞에있는 트럭(truck.peek())을 bw에 더해도 L(최대하중)보다 작아서 다리가 견딜 수 있는지 검사한다. 
 만약 작다면 건널수 있다는 뜻이므로, bw에 트럭에 무게를 더해주고, 다리 위에(q)에도 트럭의 무게만큼을 더하고, truck.poll()로 First Out 해준다. 
 만약 무게를 버틸 수 없다면, 다리위(q)에는 아무것도 안실리므로, q에 0(아무것도 없음)을 넣어준다. 

while(!bridge.isEmpty()){
            time++;
            bw -= bridge.poll();
            if(!truck.isEmpty()){
                if(truck.peek() + bw <= L){
                    bw += truck.peek();
                    bridge.offer(truck.poll());
                } else{
                    bridge.offer(0);
                }
            }
        }

 

풀면서 놓쳤던점

나 자신이 구현문제에 약하다는 것을 느꼈다.

 

이 문제를 통해 얻어갈 것

큐를 이용한 구현문제

 

내 코드 

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

class Main {

    static int n, w, L;
    static Queue<Integer> truck;

    public static void main(String[] args) throws IOException {
        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());
        truck = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            truck.offer(Integer.parseInt(st.nextToken()));
        }

        Queue<Integer> bridge = new LinkedList<>();
        for(int i = 0; i < w; i++){
            bridge.offer(0);
        }
        int time = 0;
        int bw = 0;
        while(!bridge.isEmpty()){
            time++;
            bw -= bridge.poll();
            if(!truck.isEmpty()){
                if(truck.peek() + bw <= L){
                    bw += truck.peek();
                    bridge.offer(truck.poll());
                } else{
                    bridge.offer(0);
                }
            }
        }
        System.out.println(time);

    }

}

 

참고

X

728x90