설명
강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.
예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.
Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.
다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.
입력
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.
출력
출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.
예시 입력
예시 출력
4 2 10
7 4 5 6
JavaScript
복사
8
JavaScript
복사
풀이 과정
문제의 목적은 다음과 같습니다.
N개의 트럭이 다리를 건너는 최단 시간을 구하라.
우선 다리를 건너는 조건을 알아야 합니다.
•
다리의 길이는 W 입니다. 즉, 한 개의 트럭이 다리를 지나는데 W의 시간이 소모됩니다.
•
다리는 무게제한이 있습니다. 다리에 진입한 트럭의 총 무게가 L을 넘으면 안됩니다.
위 두 조건을 가지고 문제를 풀면 쉽게 접근할 수 있습니다.
저는 두 개의 Queue를 만들어주었는데 대기 중인 트럭의 큐와 다리에 진입한 트럭의 큐입니다.
대기 중인 큐와 다리에 진입한 큐가 모두 비었다면 (즉, 모두 건넜다면) while 문은 종료됩니다.
while 문 내 조건 문은 다음과 같습니다.
•
if (!bridge.isEmpty() && bridge.peek().position == W)
만약 다리에 트럭이 한 대라도 있고, 해당 트럭이 다리의 끝에 도달했다면 다리에서 트럭을 제거합니다.
•
if (!trucks.isEmpty() && totalWeight + trucks.peek().weight <= L)
만약 대기 중인 트럭이 있고, 해당 트럭이 다리에 올라와도 무게 제약에 위배되지 않는다면 트럭을 다리에 추가합니다.
그리고 다리 위에 있는 모든 트럭을 움직여줍니다. 이 때, 스트림을 사용하여 간편하게 해결하였습니다.
private static void moveAlls(Queue<Truck> bridge) {
bridge.stream().forEach(t -> t.move());
}
Java
복사
최종 코드
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 _13335 {
public static void main(String[] args) throws IOException {
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());
Queue<Truck> trucks = new LinkedList<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
trucks.offer(new Truck(Integer.parseInt(st.nextToken())));
}
Queue<Truck> bridge = new LinkedList<>();
int totalWeight = 0;
int time = 0;
while (!trucks.isEmpty() || !bridge.isEmpty()) {
time++;
if (!bridge.isEmpty() && bridge.peek().position == W) {
totalWeight -= bridge.poll().weight;
}
if (!trucks.isEmpty() && totalWeight + trucks.peek().weight <= L) {
Truck truck = trucks.poll();
totalWeight += truck.weight;
bridge.offer(truck);
}
moveAlls(bridge);
}
System.out.println(time);
}
private static void moveAlls(Queue<Truck> bridge) {
bridge.stream().forEach(t -> t.move());
}
static class Truck {
int weight;
int position;
public Truck(int weight) {
this.weight = weight;
this.position = 0;
}
public int move() {
return ++position;
}
}
}
JavaScript
복사
