04. 가장 높은 탑 쌓기

 

 

 

설명

첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.

 

 

 

 

예시

5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

10

 

 

 

 

풀이

1. Collections. sort로 밑면넓이가 제일 큰 순서대로 내림차순 정렬을 해야한다.

 

2. 이중 for문을 돌면서

for(int i=1; i<n ;i++){

int max=0; <<< 반드시 0이어야한다. 왜냐면 내가 가장 작은 애면 내 높이가 total 배열에 들어가야함으로

 

for(int j=i-1; j>=0; j--){ << 0부터 i-1까지로 바꾸어도 상관없다.

 if(내무게<앞에것무게 && total[j]>max){

   max기억

}

 

}

}

 

 

import java.util.*;

class Brick implements Comparable<Brick>{
	int area, height, weight;
	public Brick(int area,int height, int weight) {
		this.area=area;
		this.height=height;
		this.weight=weight;
	}
	
	@Override
	public int compareTo(Brick o) {
		return o.area- this.area;
	}
}

class Main {
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n= sc.nextInt();
		
		ArrayList<Brick> list= new ArrayList<>();
		
		for(int i=0; i<n ;i++) {
			int area =sc.nextInt();
			int height =sc.nextInt();
			int weight =sc.nextInt();
			
			list.add(new Brick(area,height,weight));
		}
		
		Collections.sort(list);

		int [] total = new int[n];
		total[0]= list.get(0).height;
		
		int answer=0;
		
		for(int i=1; i<n ;i++) {
			int max=0;
			for(int j=i-1; j>=0; j--) {
				if(list.get(i).weight<list.get(j).weight &&total[j]>max) {
					max=total[j];
				}
			}
			total[i]=max+list.get(i).height;
			answer=Math.max(answer, total[i]);
		}
		

		System.out.println(answer);
		

	}

	
}