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
문제
강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 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번째 트럭의 무게를 나타낸다.
출력
출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.
이 문제는 First In First Out인 Queue를 사용해서 해결할 수 있는 문제이다.
먼저 풀이 코드는 아래와 같다.
package ALGO;
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 트럭 {
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<Integer> truck = new LinkedList<Integer>();
st = new StringTokenizer(br.readLine());
for(int i= 0; i< n; i++) {
truck.offer(Integer.parseInt(st.nextToken()));
}
int time = 0;
int bw=0;
Queue<Integer> q = new LinkedList<Integer>();
for(int i =0; i<w ; i++) {
q.add(0);
}
while(!q.isEmpty()) {
time++;
bw-=q.poll();
if(!truck.isEmpty()) {
if(truck.peek()+bw<=L) {
bw+=truck.peek();
q.offer(truck.poll());
}else {
q.offer(0);
}
}
}
System.out.println(time);
}
}
먼저 문제에서 주어진 n(트럭의 개수) , w(다리의 길이) , L(최대하중)과 주어진 순서대로 다리위로 올라오는 truck을 Queue의 형태로 받아준다.
그리고 이제 얼마나 시간이 걸릴지 계산한다.
걸릴 시간을 계산할 time과, bw(bridge Weight), 다리에 올라간 무게를 0으로 초기화한다.
그리고선 처음에는 다리가 모두 비어있고, 처음 들어오는 트럭이 지나갈 시간을 구하기 위해
다리는 Queue로 선언해 준고 여기에 다리의 길이만큼 0을 넣어준다. 다리의 길이만큼 이동하면서 Queue를 계산하게 된다.
그리고선 q 라는 다리 위에 있는 공간에 아무것도 없을 때까지 반복문(while)을 돌아주게된다.
먼저 1초가 지나고 다리에 차가 올라갈 수 있으니, time에 하나를 더해주고,
이렇게 나온 무게는 다리 밖으로 나오므로, bw(다리위무게)에서 내려운 만큼(q.poll())을 빼준다(처음 다리길이까지는 0만빠진다. )
그리고 만약 트럭이 남아있다면, if(!truck.isEmpty()) 가장 앞에있는 트럭(truck.peek())을 bw에 더해도 L(최대하중)보다 작아서 다리가 견딜 수 있는지 검사한다.
만약 작다면 건널수 있다는 뜻이므로, bw에 트럭에 무게를 더해주고, 다리 위에(q)에도 트럭의 무게만큼을 더하고, truck.poll()로 First Out 해준다.
만약 무게를 버틸 수 없다면, 다리위(q)에는 아무것도 안실리므로, q에 0(아무것도 없음)을 넣어준다.
이렇게 제한하중보다 작으면 q에 Fisrt In하고, 다리 길이만큼 지나면 First Out을 해주면서 모든 트럭(truck)이 남아있지 않고, 다리(q) 위에도 아무 것도 없을 때까지 반복문(while)을 돌게된다.
q에 남아있는 값이 없다면, 모든 트럭이 다리를 지난 것이므로,
답을 출력한다.