[JAVA] 백준 13335 - 트럭

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

문제 이해

트럭은 오른쪽에서 왼쪽으로 시간 1마다 길이1씩 움직일 수 있다.

여러개의 트럭이 한번에 1씩 움직일수도 있다.

다리 위에 올라갈 수 있는 트럭은 무게가 제한되어 있으므로 이를 주의해야 한다.

문제 풀이

큐를 이용하여 풀었다.

큐는 다리를 나타낸다. 제일 처음에 다리길이만큼 큐에 0을 삽입한다.

그리고 트럭이 1씩 움직이는데 다리 위에 있는 트럭 무게의 합을 기준으로 새로운 트럭을 올릴지말지 결정한다.

큐에서 한개 뺀 무게와 새로운 트럭의 합이 L(최대하중) 이하이면 트럭을 새로 다리 위에 올릴 수 있다. 만약 L 초과면 트럭을 못올리기 때문에 0을 큐에 삽입한다.


이렇게 모든 트럭이 다리를 지나거나 올라갈 때까지 반복을 해준다. 더이상 올릴 새로운 트럭이 없으면 반복문을 중단하고 큐에 머물러 있는 인자 갯수만큼 시간을 추가해주고 끝난다.

코드

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Back13335 {

	static int N, W, L; //트럭 수, 다리길이, 최대하중
	static Queue<Integer> bridge = new ArrayDeque<Integer>();
	static int sum; //다리 위에 있는 트럭 무게 합
	
	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());
		
		for (int i = 0; i < W; i++) { //다리길이만큼 큐에 0 넣어줌 
			bridge.add(0);
		}
		
		//초기화
		sum = 0;
		int time = 0;
		
		st = new StringTokenizer(br.readLine());
		int truck = Integer.parseInt(st.nextToken());
		
		while(true) { //더이상 넣을 트럭이 없을때까지 반복 (반복 1번에 시간+1)
			time++; 
			
			sum-=bridge.poll();
			if(sum+truck <= L) { //새로운 트럭이 다리를 건널 수 있을 때
				bridge.add(truck);
				sum+=truck;
				if(--N == 0) break; //더이상 새로운 트럭이 없으면 중단
				
				truck = Integer.parseInt(st.nextToken());
				
			}else { //새로운 트럭이 다리를 건널 수 없을 때 -> 0을 인자로 넣어주고 기다리게 함
				bridge.add(0);
			}
			
		}
		
		time += bridge.size(); //다리에 남아있는 트럭들 건너는 시간 합함
		System.out.println(time);
	}
}