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
풀이 방법
큐를 이용하여 구현한다.
대기 트럭의 큐 , 다리 위 트럭의 큐 총 2개의 큐를 만든다.
다리 위 트럭의 큐는 (트럭의 무게, 트럭의 위치) 를 저장한다.
시간을 1초씩 증가시키면서 매초마다 큐의 상태를 확인하고 갱신하는 데 알고리즘 흐름은 아래와 같다.
1. 초기 대기 트럭의 큐에 모든 트럭을 삽입한다.
2. 다리 위 트럭들의 위치를 모두 앞으로 1씩 이동시킨다.
3. 다리 위 맨 앞의 트럭의 위치가 0이 되면 pop 하여 제거한다.
4. 대기 큐의 맨 앞 트럭이 다리를 건널 수 있는지 확인하고 대기 큐에서 pop 하여 다리 큐에 넣는다.
(다리 위에 트럭이 W개 이상이 되지 않고 최대하중이 L 을 넘지 않아야 한다.)
5. 대기 큐와 다리 큐 모두 트럭이 없을 때까지, 즉 모든 트럭이 다리를 건널 때까지 2~4번의 과정을 반복한다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] lines = br.readLine().split(" ");
int n = Integer.parseInt(lines[0]); // 다리를 건너는 트럭의 수
int w = Integer.parseInt(lines[1]); // 다리의 길이
int l = Integer.parseInt(lines[2]); // 다리의 최대하중
Queue<Integer> readyTrucks = new LinkedList<>(); // 대기 중인 트럭
Queue<int[]> moveTrucks = new LinkedList<>(); // 다리 위를 건너는 트럭
lines = br.readLine().split(" ");
for(int i=0; i<n; i++) {
readyTrucks.add(Integer.parseInt(lines[i])); // 대기 중인 트럭 큐에 삽입
}
int time = 0; // 총 걸린 시간
int totalWeight = 0; // 다리 위 트럭들의 총 무게 합
while(!readyTrucks.isEmpty() || !moveTrucks.isEmpty()) { // 모든 트럭이 다 건널 때까지
// 다리 위 트럭의 위치를 1만큼 앞으로 옮김
for(int[] truck : moveTrucks) {
truck[1] -= 1;
}
// 맨 앞 트럭이 다리를 다 건너면 제거
if(!moveTrucks.isEmpty() && moveTrucks.peek()[1] == 0) {
totalWeight -= moveTrucks.poll()[0];
}
// 맨 앞 대기 중인 트럭이 다리를 건널 수 있는 지 최대하중과 다리의 길이 비교
if(!readyTrucks.isEmpty() && readyTrucks.peek() + totalWeight <= l && moveTrucks.size() < w) {
int weight = readyTrucks.poll(); // 현재 트럭의 무게
totalWeight += weight; // 다리 위 트럭의 무게에 추가
moveTrucks.add(new int[]{weight, w}); // 다리 위 트럭에 삽입
}
time++;
}
System.out.println(time);
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 16235 나무 재테크 자바(java) (0) | 2023.12.19 |
|---|---|
| 백준 1182 부분수열의 합 자바(java) (0) | 2023.12.05 |
| 백준 1360 되돌리기 자바(java) (0) | 2023.11.17 |
| 백준 19640 화장실의 규칙 자바(java) (0) | 2023.11.16 |
| 백준 11067 모노톤길 자바(java) (1) | 2023.11.16 |