문제 url : https://www.acmicpc.net/problem/13335
문제 내에 여러 조건이 있지만, 중요 단서 몇 개만 제대로 파악하고 확인할 수 있으면 된다. 아래와 같이 정리해볼 수 있다.
문제를 풀면서 헷갈린 조건들은 굵게 표시해보았다.
더보기
* n 개의 트럭이 다리를 건넌다. (순서는 바꿀 수 없다.)
* 다리 위에는 w대의 트럭만 동시에 올라갈 수 있으며, 다리를 건너는 시간 또한 각 트럭당 w의 시간이 걸린다.
* 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다.
* 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다
내가 작성한 코드는 아래와 같다.
import java.util.*;
import java.io.*;
public class Main {
static int[] trucks;
static int n,w,l;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// n : 트럭 개수
// w : 다리 길이
// L : 최대 하중
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
trucks = new int[n+1];
st = new StringTokenizer(br.readLine());
for(int i=1; i<=n; i++) {
trucks[i] = Integer.parseInt(st.nextToken());
}
solution();
}
static void solution() {
Queue<Integer> queue = new LinkedList<>();
int curWeight = 0; // 현재 다리 위의 무게
int time = 0;
for(int i=1; i<=n; i++) {
int truck = trucks[i];
while(true) {
// 트럭 없는 경우
if(queue.isEmpty()) {
queue.add(truck);
curWeight += truck;
time++;
System.out.println(i + "번쨰 트럭(" + trucks[i] + ")이 비어있는 Queue에 추가되었습니다. 현재 다리 무게 : " + curWeight + ", 현재 시각: " + time);
break;
}
// 트럭 가득 찬 경우
else if (queue.size() == w) {
curWeight -= queue.poll();
System.out.println(i + "번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : " + curWeight);
}
// 트럭 추가할 수 있는 경우
else {
if(curWeight + truck <= l) {
queue.add(truck);
curWeight += truck;
time++;
System.out.println(i + "번쨰 트럭(" + trucks[i] + ")이 Queue에 추가되었습니다. 현재 다리 무게 : " + curWeight + ", 현재 시각: " + time);
break;
} else {
// 트럭이 한 칸씩 움직임
queue.add(0);
time++;
System.out.println(i + "번쨰에서 트럭이 한 칸 움직입니다. 이때 시간 : " + time);
}
}
}
}
time += w;
System.out.println(time);
}
}
진행과정 설명을 위해 각 단계에 출력 코드를 넣어보았다.
실행 결과는 아래와 같이 나온다.
4 2 10
7 4 5 6
1번쨰 트럭(7)이 비어있는 Queue에 추가되었습니다. 현재 다리 무게 : 7, 현재 시각: 1
2번쨰에서 트럭이 한 칸 움직입니다. 이때 시간 : 2
2번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 0
2번쨰 트럭(4)이 Queue에 추가되었습니다. 현재 다리 무게 : 4, 현재 시각: 3
3번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 4
3번쨰 트럭(5)이 Queue에 추가되었습니다. 현재 다리 무게 : 9, 현재 시각: 4
4번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 5
4번쨰에서 트럭이 한 칸 움직입니다. 이때 시간 : 5
4번쨰에서 다리가 가득 찼습니다, 현재 무게가 변경되었습니다. 현재 무게 : 0
4번쨰 트럭(6)이 Queue에 추가되었습니다. 현재 다리 무게 : 6, 현재 시각: 6
8
Queue에는 현재 다리위에 있는 트럭을 의미한다. 이때, 0을 추가하는 이유가 있다. 이유가 뭘까?
Queue에서 나온 트럭의 무게를 이용해 현재 다리위의 무게를 계산한다. 트럭은 다리를 건널 때, 매 초마다 한 칸씩 이동하게 되는데, 만약 다리 위에 있는 트럭이 끝까지 다리를 건너지 못했다면, 다른 트럭이 다리에 올라가길 기다려야 한다. 트럭이 한 칸씩 이동하는 동안, 그 자리를 유지하기 위해 큐에 0을 추가하는 것이다. 즉, 0을 추가한다는 것은 트럭이 다리를 한 칸 이동하면서 뒤의 트럭이 기다리고 있다는 것을 의미한다.
출력문을 토대로, 직접 그려가며 문제를 풆다 보면 쉽게 이해할 수 있을 것이다.
소요시간 : 1시간 15분