#13335 : 트럭

풀이방법

사용된 것:

Queue

 

2022.04.30

2개의 큐를 사용하여 푸는 문제이다.

 

다리에 아직 올라가지 않은 트럭들을 저장하는 Queue<Integer> trucks

다리 위의 상태를 저장하는 Queue<Integer> bridge

 

이렇게 2개를 사용하였다.

 

trucks의 각 요소는 한 대의 트럭마다 할당된다. 각각 해당 트럭의 무게를 저장한다.

bridge의 각 요소는 하나의 단위길이마다 할당된다. 각각 해당 단위길이에 실린 무게를 저장한다.

 

백준 문제 페이지의 1번 예제의 경우에 위 2개 큐의 초기상태는 다음과 같다.

1번 예제의 입력값:

4 2 10
7 4 5 6

 

trucks의 초기 상태는 다음과 같다.

7

4

5

6

 

bridge의 초기 상태는 다음과 같다.

아직 아무 트럭도 다리 위에 올라가지 않았으므로 두 개의 단위길이 모두 0의 하중이 실려있다.

0

0

 

 

지금까지 지난 단위시간을 저장하는 int형 변수 time을 선언하고 0으로 초기화한다.

현재 다리 위에 올라온 모든 트럭의 무게의 합을 저장하는 int형 변수 sum을 선언하고 0으로 초기화한다.

 

이제 한 단위시간마다 다음의 과정을 수행하면 문제가 해결된다.

 

일단 time을 1 증가시켜준다.

 

int형 변수 out을 선언한다.

이 변수는 이번 단위시간에 다리에서 나가는 무게를 가리킨다.

따라서 bridge에서 요소 하나를 poll()하여 out에 저장해둔다.

 

int형 변수 in을 선언한다.

이 변수는 이번 단위시간에 다리에 들어올 수도 있는 트럭의 무게를 가리킨다.

따라서 trucks에서 요소 하나를 peek()하여 in에 저장해둔다.

 

sum에 in을 더한 값이 L 이하인지 확인한다.

만약 L 이하라면 이번 단위시간에 트럭이 한 대 다리에 들어올 수 있는 것이다. sum의 값을 in만큼 증가시키고, bridge에도 in을 add()해준다. trucks에서는 요소 하나를 poll()한다.

만약 L을 초과한다면 이번 단위시간에는 트럭이 다리에 들어올 수 없다. bridge에 0을 add()해주고, trucks는 건드리지 않는다.

 

이 과정을 trucks가 빌 때까지, 즉 모든 트럭이 다리 위에 올라갈 때까지 반복한다.

 

 

 

마지막으로,

모든 트럭이 다리 위에 올라간 시점 이후 정확히 w단위시간이 지난 뒤 모든 트럭이 다리에서 빠져나가므로 time에 w를 더해준다.

 

time을 화면에 출력하면 문제가 해결된다.

 

 

코드

Java(2022.04.30)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//n, w, l
		int n = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());		
		
		//필요한 변수들 선언
		//아직 다리에 올라가지 않은 트럭들을 저장할 큐
		Queue<Integer> trucks = new LinkedList<Integer>();
		//다리 위의 상황을 저장할 큐
		Queue<Integer> bridge = new LinkedList<Integer>();
		//현재 다리 위에 있는 트럭들의 무게 총합
		int sum = 0;
		//걸린 단위시간의 크기(정답)
		int time = 0;
		
		
		//트럭 무게 정보 읽어오기
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) trucks.add(Integer.parseInt(st.nextToken()));
		//다리 상태 초기화하기(비어있는 단위길이에는 0을 저장함)
		for(int i = 0; i<w; i++) bridge.add(0);
		
		
		//여기부터 문제해결
		//모든 트럭이 다리 위에 올라갈 때까지 반복
		while(!trucks.isEmpty()) {
			//시간이 흐름
			time++;
			
			//이번에 다리에서 빠져나가는 무게
			int out = bridge.poll();
			//이번에 다리에 들어갈 수도 있는 무게
			int in = trucks.peek();
			
			//빠져나가는 무게 처리
			sum -= out;
			
			//이번 트럭이 올라갔을 때 다리 위의 트럭 무게가 l 이하이면 트럭 넣기
			if(sum + in <= l) {
				bridge.add(in);
				sum += in;
				trucks.poll();
			}
			//그렇지 않으면 0 넣기
			else bridge.add(0);
		}
		//모든 트럭이 다리 위에 올라간 순간부터 w초 뒤에 모든 트럭이 다리를 빠져나가므로 시간에 w 더하기
		time += w;
		
		//정답 출력
		System.out.print(time);

	}

}