Repository navigation
Expand file tree
/
Copy pathMain_4.java
More file actions
71 lines (61 loc) · 1.87 KB
/
Copy pathMain_4.java
File metadata and controls
71 lines (61 loc) · 1.87 KB
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
package inflearn.dp;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/*
* 가장 높은 탑 쌓기
* */
public class Main_4 {
static int[] dy;
static class Brick implements Comparable<Brick> {
int s; // 넓이
int h; // 높이
int w; // 무게
public Brick(int s, int h, int w) {
this.s = s;
this.h = h;
this.w = w;
}
@Override
public int compareTo(Brick o) {
/*
* 0 = 같은 수
* 음수 = 작은 수
* 양수 = 큰 수
* */
return this.s - o.s; // 오름차순
// return o.s - this.s; // 내림차순
}
}
public int solution(ArrayList<Brick> brickArrayList) {
int answer = 0;
Collections.sort(brickArrayList);
dy[0] = brickArrayList.get(0).h;
answer = dy[0];
for (int i = 0; i < brickArrayList.size(); i++) {
int maxHeight = 0;
for (int j = i - 1; j >= 0; j--) {
if (brickArrayList.get(j).w > brickArrayList.get(i).w && dy[j] > maxHeight) {
maxHeight = dy[j];
}
}
dy[i] = maxHeight + brickArrayList.get(i).h;
answer = Math.max(answer, dy[i]);
}
return answer;
}
public static void main(String[] args) {
Main_4 main = new Main_4();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Brick> brickArrayList = new ArrayList<>();
dy = new int[n];
for (int i = 0; i < n; i++) {
int s = sc.nextInt();
int h = sc.nextInt();
int w = sc.nextInt();
brickArrayList.add(new Brick(s, h, w));
}
System.out.println(main.solution(brickArrayList));
}
}