개발 다이어리

코드

import java.util.ArrayList;
import java.util.Collections;

/**
 * 벽돌은 가장 넓은 것이 아래에 위치
 * 그리고 가장 무거운 것일 수록 아래 위치
 */
public class 가장높은탑쌓기{

	static class Brick implements Comparable<Brick>{
		public final int width, heigth, weight;
		public Brick(int width, int heigth, int weight) {
			this.width = width;
			this.heigth = heigth;
			this.weight = weight;
		}
		public int compareTo(Brick o){
			return o.width-this.width;
		}
	}
	
	static int[] dy;
	static ArrayList<ArrayList<Brick>> list;
	
	public static void main(String[] args){
		int[][] input = 
			{
					{25, 3, 4 }
					,{4 ,4 ,6  }
					,{9 ,2 ,3  }
					,{16, 2, 5 }
					,{1 ,5 ,2  }
			};
		int n=input.length;
		
		ArrayList<Brick> arr=new ArrayList<>();
		
		dy=new int[n];
		for(int i=0; i<n; i++){
			int a= input[i][0] ;
			int b= input[i][1] ;
			int c= input[i][2] ;
			arr.add(new Brick(a, b, c));
		}
		System.out.print(solution(arr));
	}
	
	static int solution(ArrayList<Brick> arr){
		//너비 순으로 내림차순
		Collections.sort(arr);
		dy[0]=arr.get(0).heigth;
		int answer= dy[0];
		
		//높이 비교 1부터
		for(int i=1; i<arr.size(); i++){
			//높이 tmp
			int max_h=0;
			//이전 벽돌 비교
			for(int j=i-1; j>=0; j--){
				//무게는 j가 커야한다. 그리고 그 중에 제일 높은 값을 구한다.
				if(arr.get(j).weight > arr.get(i).weight && dy[j]>max_h){
					max_h=dy[j];
				}
			}
			//제일 높은 값을 구했으니, 그 값에 나의 높이를 더 한다.
			dy[i]=max_h+arr.get(i).heigth;
			//지금까지 높이 중 가장 큰 높이를 구한다.
			answer=Math.max(answer, dy[i]);
		}
		return answer;
	}
}

결과

10

이전 최대부분증가수열과 거의 같다. 

일부 특수화가 됐을 뿐이다.

코드

import java.util.Arrays;

public class 최대부분증가수열연습 {
	static int dy[];
	
 	public static void main(String[] args) {
 		//수열
		int[] arr = {5, 3, 7, 8, 6, 2, 9, 4};
		System.out.println(solution(arr));
	}
	static int solution(int[] arr) {
		int answer = 0;
		dy = new int[arr.length];
		dy[0] = 1;
		//수열 순회
		for(int i=1;i<arr.length;i++) {
			//수열 수 저장
			int max = 0;
			//현재 수열 이전 값 중 작은 값있는지 탐색
			for(int j=i;j>=0;j--) {
				//현재 수열보다 작은 값 있으면, 거기에 저장된 수열 횟수 저장
				if(arr[i]>arr[j]) {
					max = Math.max(max, dy[j]);
				}
			}
			//구해진 수열 수에 +1
			dy[i] = max+1;
			//최종적으로 가장 횟수 많은 부분 수열을 구함
			answer = Math.max(answer, dy[i]);
		}
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(dy));
		return answer;
	}
}

결과

[5, 3, 7, 8, 6, 2, 9, 4]
[1, 1, 2, 3, 2, 1, 4, 2]
4

9가 있는 위치를 기준으로 설명

이 기준으로 탐색을 시작

그 값에 +1을 한 것

왜 3을 찾아서 +1을 했는가?

8을 기준으로 하면 최대 부분 증가 수열은 3이다.

5-7-8 or -3-7-8  3개

9 값이전에서 가장 큰 최대 부분 증가 수열 수는 3이다.

그 값에 +1을 한 것

바텀업 방식으로 값을 구한 것이다.

문제의 본질을 유지한 상태로 작은 케이스부터 큰 케이스를 탐색하는 방식