8980번: 택배
입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이
www.acmicpc.net
처음에는 보내는 마을 기준으로 오름차순 정렬하였으나, 반례를 만나고 소스를 갈아엎고 받는 마을 기준으로 오름차순 정렬하였습니다.
우선 to배열에는 해당 마을을 지날때 최대용량으로 초기화를 시켜놓았습니다.
다음은 예제로 설명을 하겠습니다.
4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20N = 4, C = 40, M = 6
택배 정보를 받는 마을 기준으로 정렬하면 이렇게됩니다. to[1] = 40, to[2] = 40, to[3] = 40
1 2 10
1 3 20
2 3 10
1 4 30
2 4 20
3 4 20이제 1 -> 2로 10만큼을 보냅니다.
도착마을인 2를 제외하고 1 -> 2 경로에 있는 마을의 남은 용량의 최소는 40으로 10보다 큽니다.
그러면 to[1]에서 10만큼 빼줍니다.
(ans = 10)
to[1] = 30, to[2] = 40, to[3] = 40
다음 1 -> 3으로 20만큼 보냅니다.
도착마을인 3을 제외하고 1 -> 3 경로에 있는 마을의 남은 용량의 최소는 30으로 20보다 큽니다.
그러면 to[1]와 to[2]에서 20만큼 빼줍니다.
(ans = 10 + 20 = 30)
to[1] = 10, to[2] = 20, to[3] = 40
다음 2 -> 3으로 10만큼 보냅니다.
도착마을인 3을 제외하고 2 -> 3 경로에 있는 마을의 남은 용량의 최소는 20으로 10보다 큽니다.
그러면 to[2]에 10만큼 빼줍니다.
(ans = 30 + 10 = 40)
to[1] = 10, to[2] = 10, to[3] = 40
다음 1 -> 4로 30만큼 보냅니다.
도착마을인 4를 제외하고 1 -> 4 경로에 있는 마을의 남은 용량의 최소는 10으로 30보다 작습니다.
따라서 남은 용량의 최소만큼인 10만큼 빼줍니다.
(ans = 40 + 10 = 50)
to[1] = 0, to[2] = 0, to[3] = 40
다음 2 -> 4로 20만큼 보냅니다.
도착마을인 4를 제외하고 2 -> 4 경로에 있는 마을의 남은 용량의 최소는 0이므로 보낼 수 없습니다.
(ans = 50)
to[1] = 0, to[2] = 0, to[3] = 40
다음 3 -> 4로 20만큼 보냅니다.
도착마을인 4를 제외하고 3 -> 4 경로에 있는 마을의 남은 용량의 최소는 40으로 20보다 큽니다.
그러면 to[3]에 20만큼 빼줍니다.
(ans = 70)
to[1] = 0, to[2] = 0, to[3] = 20
과정이 모두 끝났으니 ans를 출력해줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<int[]> list = new ArrayList<>();
static int to[];
static int N, C, M, ans;
static void func() {
for (int i = 0; i < M; i++) {
int u = list.get(i)[0];
int v = list.get(i)[1];
int c = list.get(i)[2];
int maxC = Integer.MAX_VALUE;
for (int j = u; j < v; j++)
maxC = Math.min(maxC, to[j]);
if (maxC >= c) {
for (int j = u; j < v; j++)
to[j] -= c;
ans += c;
} else {
for (int j = u; j < v; j++)
to[j] -= maxC;
ans += maxC;
}
}
System.out.println(ans);
}
static void input() throws Exception {
int u, v, c;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
to = new int[N + 1];
Arrays.fill(to, C);
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
list.add(new int[] { u, v, c });
}
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[1] == b[1])
return a[0] - b[0];
else
return a[1] - b[1];
}
});
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 13904 과제 (0) | 2021.09.30 |
|---|---|
| boj 1826 연료 채우기 (0) | 2021.02.22 |
| boj 11000 강의실 배정 (0) | 2021.02.16 |
| boj 1931 회의실 배정 (0) | 2021.02.16 |
| boj 2839 설탕 배달 (0) | 2021.02.16 |