Problem
Solve
도착마을 기준 오름차순으로 놓고 찾으려니 일부의 택배를 계산하지 못해 다른 분의 코드를 참고했다.
도착 마을을 기준으로 오름차순을 하는 이유는 내리는 마을이 빠를 수록 택배를 빨리 내리고 다른 택배를 실을수 있기 때문이다.
주어진 택배 정보는 아래와 같다.
받는 마을을 기준으로 오름차순 정렬을 하면 아래와 같다.
여기서 각 마을에서 받는 택배의 용량을 최대로 설정해 놓은 다음, 받는 마을이 가장 가까운 순으로 보내는 마을부터 받는 마을-1 까지의 마을에 택배의 개수만큼 차감하게 된다면 뒤에 택배를 보낼때 남은 택배 용량에 맞춰 택배를 나눠서 보낼수 있게 된다.
1번, 2번, 3번 마을에 택배의 최대 용량으로 설정한다.
4번 마을에서는 택배를 받지 않으므로 제외한다.
10개의 택배를 1번 마을에서 보내고 2번 마을에서 받을 때
1번 마을에서 10개의 택배를 보내게 되면 1번 마을에서 보낼수 있는 택배의 용량은 30개가 된다.
20개의 택배를 1번 마을에서 보내고 3번 마을에서 받을 때
1번 마을과 2번 마을에 20개의 택배가 있게 되고 각각 10과 20개의 택배만 받을수 있게 된다.
10개의 택배를 2번 마을에서 보내고 3번 마을에서 받을 때
2번 마을에서 허용가능한 택배 용량은 20이므로 10개의 택배를 받을 수 있다.
30개의 택배를 1번 마을에서 보내고 4번 마을에서 받을 때
1번과 2번마을에서 받을 수 있는 택배 용량은 10개이므로 30개의 모든 택배를 4번 마을까지 보낼수 없다. 그렇기 때문에 1,2,3 번 마을 중 가장 작은 택배 용량인 10개만 나눠서 보낼수 있다.
20개의 택배를 2번마을에서 4번 마을에서 받을 때 2번마을에서는 택배를 실을수 없다.
20개의 택배를 3번 마을에서 보내고 4번 마을에서 받을 때
3번 마을에서는 30개의 택배를 받을 수 있는 여유가 있기 때문에 20개의 택배를 모두 보낼수 있다.
총 70개의 택배를 보낼수 있게 된다.
Code
public class 택배 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//마을 수
int N = Integer.parseInt(st.nextToken());
//트럭 용량
int C = Integer.parseInt(st.nextToken());
//박스 개수
int M = Integer.parseInt(br.readLine());
//받는 마을 기준 오름차순 정렬
PriorityQueue<Box> boxes = new PriorityQueue<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int send = Integer.parseInt(st.nextToken()) - 1;
int receive = Integer.parseInt(st.nextToken()) - 1;
int size = Integer.parseInt(st.nextToken());
boxes.offer(new Box(send, receive, size));
}
//각 마을에서 실을 수 있는 택배의 용량
int[] maxBoxSize = new int[N];
Arrays.fill(maxBoxSize, C);
int answer = 0;
for (Box box : boxes) {
int maxSize = 10000;
for (int i = box.send; i < box.receive; i++) {
//각 마을에서 실을 수 있는 택배 용량의 최소
maxSize = Math.min(maxBoxSize[i], maxSize);
}
//실을 수 있는 택배 용량의 최소와 실으려는 택배의 크기 중 작은 것을 실는다.
maxSize = Math.min(maxSize, box.size);
//실을 수 있는 택배 용량만큼 감소시킨다.
for (int i = box.send; i < box.receive; i++) {
maxBoxSize[i] -= maxSize;
}
//실은 택배 개수 갱신
answer += maxSize;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
static class Box implements Comparable<Box> {
int send;
int receive;
int size;
public Box(int send, int receive, int size) {
this.send = send;
this.receive = receive;
this.size = size;
}
@Override
public int compareTo(Box o1) {
int answer = this.receive - o1.receive;
if (answer == 0) {
answer = this.send - o1.send;
}
return answer;
}
}
}
Result
Reference
