[백준 13335번] 트럭 with Java

guswls·2024년 5월 6일

알고리즘

목록 보기

21/39

문제

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

코드

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

//4 2 10
//7 4 5 6
//-> 8
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
		Queue<Integer> trucks = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			trucks.add(Integer.parseInt(st.nextToken()));
		}

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

		int time = 0;
		int weightOnBridge = 0;
		while (!bridge.isEmpty()) {
			time++;
			weightOnBridge -= bridge.poll();
			
			//트럭이 비어있으면 건너뜀
			if(trucks.isEmpty()) {
				continue;
			}
			
			// 만약 다리 위를 트럭이 지나갈 수 있으면
			if (trucks.peek() + weightOnBridge <= L) {
				//트럭큐에서 트럭 한개를 꺼내서 다리큐에 놓고, 현재 다리에 있는 트럭 무게 갱신
				int cur = trucks.poll();
				weightOnBridge += cur;
				bridge.add(cur);
			}else {
				//지나갈 수 없으면 0 삽입
				bridge.add(0);
			}
		}

		System.out.println(time);

	}
}

문제 이해

무게가 다른 트럭 여러 개가 다리를 건너려고 한다. 이때 모든 트럭이 다리를 건너는 최소 시간을 구하는 문제이다.
입력으로는 트럭 개수, 다리 길이, 다리의 최대 하중이 주어지고, 다음 라인에 각 트럭의 무게들이 주어진다.
다리길이 1을 이동하는데 드는 소요시간은 1이다.
그리고 트럭의 순서는 고정되어있으며 여러개의 트럭이 줄지어 건널수도 있다.
단, 최대 하중을 초과하여 다리를 건널 수는 없다.
그리고 트럭의 개수가 다리의 길이를 초과하면 안된다.

풀이 방법

트럭을 답고 있는 큐 하나, 각 시간별 다리의 상황을 답고 있는 큐 하나 총 두개를 사용하였다.
bridge큐에는 현재 건너고 있는 트럭의 무게가 위치별로 들어있으며, 아무 트럭도 존재하지 않는 위치에는 0이 들어있다.
while문 내부 로직은 다음과 같다.
1. while문 시작마다 time을 증가시키고, bridge큐에서 값을 하나 뺀 다음에 weightOnBridge변수에서 그 값을 뺸다.
  만약 해당 지점에 트럭이 없었다면, 0을 뺄것이고 트럭이 존재했다면 건너간 트럭 무게만큼 빠질 것이다.
2. 만약 모든 트럭이 큐에서 빠져나갔다면 아래 로직을 건너뛴다.
  트럭 큐에서 모두 빠졌더라도, 다리에 존재하는 트럭이 모두 다리를 건넌것은 아니기 때문에 위 로직만 수행된다.
3. 현재 큐에 존재하는 트럭의 무게와 weightOnBridge의 합이 L보다 작다면 트럭이 다리를 건널 수 있는 상황이다. 따라서 트럭큐에서 트럭을 제거하고, weightOnBridge를 갱신한다.
4. 만약 트럭이 다리에 오를 수 없는 상황이면 bridge에 0값을 추가한다.
5. 위 동작을 반복하면서 마치 컨베이어벨트와 같이 동작하게 된다.

핵심 포인트

큐 두개를 사용해야 한다. bridge큐를 활용하고, 만약 트럭을 추가할 수 있으면 그 값을 추가하고 없으면 0을 추가한다.
이러한 동작을 통해 bridge가 현재 다리의 상태를 나타내게 된다.
bridge큐는 최초에 0으로 삽입한 후에 while문에서 poll을 하고 0또는 트럭을 add하면서 다리에 있는 트럭의 개수가 자연스럽게 W를 초과하지 않게 된다.

보완할 점 / 느낀 점

처음 풀었을 때는 bridge큐를 사용하지 않았다.
단지 while문에서 트럭을 빼내고, 다리에 존재하는 트럭의 개수와 다리의 길이를 적절히 조합해서 "한 무리"의 트럭이 지나가는 시간을 구하고 더하는 방법으로 해결하려 했다.
하지만 테케가 모두 맞고 반례들도 맞았음에도 계속 문제를 틀렸었고, 구글링을 통해 다른 풀이를 찾아봤다.
다리의 상황을 큐로 나타낸다는 개념이 매우 신박한 문제라고 생각한다. 이 문제도 꼭 다시 풀어봐야겠다.