문제
강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.
예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.
다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.
[입력]
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 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번째 트럭의 무게를 나타낸다.
[출력]
출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.
[풀이 코드]
import java.util.*;
import java.io.*;
public class Main {
static int n, w, L;
static int[] arr;
static class Point {
int w, value;
Point(int w, int value) {
this.w=w;
this.value=value;
}
}
public static void main(String[] args) throws Exception{
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()); // 다리 최대하중
st = new StringTokenizer(br.readLine());
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int cnt=0;
int idx=0;
List<Point> list = new ArrayList<>();
while(true) {
cnt++;
for(int i=0; i<list.size(); i++) {
list.get(i).w--;
if(list.get(i).w == 0) {
list.remove(i--);
}
}
int sum=0;
for(int i=0; i<list.size(); i++) {
sum+=list.get(i).value;
}
if(idx < n && sum + arr[idx] <= L) {
list.add(new Point(w, arr[idx++]));
}
if(idx==n && list.isEmpty()) break;
}
System.out.println(cnt);
}
}전형적인 시뮬레이션 문제다.
list는 현재 다리 위에 올라간 트럭을 나타내고, while 문을 돌면서 시뮬레이션을 시작한다.
첫 번째로 list의 갯수만큼 반복문을 돌면서 각 트럭마다 가지고 있는 다리 길이인 w를 1씩 감소한다. 이 과정에서 w가 0이되면 다리를 다 건넜다고 판단하므로 list에서 트럭을 제거한다.
두 번째로 list에 있는 트럭의 값을 sum 이라는 변수에 더한다.
세 번째로 이전에 구한 sum과 현재 idx에 있는 트럭을 더했을 때 L 이하이면 list에 트럭을 추가한다.
그리고 idx가 n이고 list가 비었을 경우 모든 트럭이 다리 위를 지나간 경우이기 때문에 break 문으로 while 문을 탈출한다.
