[백준 / BOJ] 13335 트럭 (Java)

문제

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

13335번: 트럭

n개의 트럭이 길이 w인 다리를 지나야한다.

다리가 견딜수있는 최대 무게가 L이라할때, n개의 트럭이 모두 지나기 위해서 걸리는 시간을 구하는 문제다.

 

---

풀이

구현 문제였다.

 

로직은 아래와 같다.

 

1. 다리의 현재 상태를 저장하는 큐를 하나 만든다. 이 큐에는 트럭이 다리에 진입한 시간, 무게가 저장될것이다.

 

2. 다리가 새로운 트럭을 수용할수없다면, 수용할수있을때까지, 큐를 비워준다.

- 이때, 큐를 비우는 조건은 다음과 같다.

 

현재시간을 time, 트럭이 다리에 최초로 진입한 시간을 initTime이라할때, 트럭의 위치는 time - initTime이다. 따라서, time - initTime이 다리의 길이를 넘어섰다면, 큐를 비워준다.

 

3. 모든 과정을 끝낸후, 다리를 전부 비워준다.

 

이후 time을 출력하면 답이다.

 

주요 소스코드

    private void queueOperate(int weight){
        this.time++;
        while(bridgeState.size() >= w || bridgeWeight+weight > L){
            if(time - bridgeState.peek().initTime >= w){
                bridgeWeight -= bridgeState.peek().weight;
                bridgeState.poll();
            }
            else time++;
        }
        bridgeWeight += weight;
        bridgeState.add(new Truck(time, weight));
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/13335%20%ED%8A%B8%EB%9F%AD/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃