[BaekJoon] 2655 가장높은탑쌓기 (Java)

🔗 문제 링크

https://www.acmicpc.net/problem/2655

📝 문제 풀이 방법

처음 문제를 풀이한 방법은 다음과 같다.
1. 벽돌을 너비 기준으로 내림차순으로 정렬한다.
2. N개의 벽돌에 대한 Dynamic pramming을 하기 위해 NxN의 배열을 만든다.
3. 2중 loop를 통해 각각의 벽돌 위에 현재 벽돌이 올라갈 수 있는지 체크를 하며 벽돌을 올릴 수 있으면 이전의 높이에 현재 벽돌의 높이를 더한다.
4. 마지막 배열에서 가장 값이 큰 값을 찾으며 해당 column을 역추적해가며 높이가 변경 될 때의 벽돌(쌓인 벽돌)을 찾아낸다.

※ 기서 현재 벽돌이란 각각의 row에 위치한 벽돌을 의미하며 index에는 각각 id/area/weight 순으로 값이 적혀있다.
※ 배열의 안에는 현재의 높이가 들어간다.

해당 풀이법은 주어진 테스트 케이스에서는 코드가 수행되었으나 코드 제출을 하였을 때는 실패를 하였습니다... 실패하는 케이스에 대해 아시는 분이 있으시다면 알려주세요😥😥

👨🏻‍💻 처음 작성한 코드 (실패)

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		ArrayList<Brick> list = new ArrayList<>();
		
		for (int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int area = Integer.parseInt(st.nextToken());
			int height = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			list.add(new Brick(i+1, area, height, weight));
		}
		
        // 넓이 기준으로 정렬하기
		Collections.sort(list);
		
		int[][] dp = new int[n][n];
		dp[0][0] = list.get(0).height;
		
		for (int i=1; i<n; i++) {
			dp[i][i] = list.get(i).height;
			for (int j=0; j<i; j++) {
				if (list.get(i).weight < list.get(j).weight) {
					dp[i][j] = dp[i-1][j] + list.get(i).height;
				}
				else dp[i][j] = dp[i-1][j];
			}
		}

		// 가장 높은 높이 찾기
		int maxHeight = -1;
		int maxHeightIndex = -1;
		for (int i=0; i<n; i++) {
			if (dp[n-1][i] > maxHeight) {
				maxHeight = dp[n-1][i];
				maxHeightIndex = i;
			}
		}
		
		// 해당 line의 값을 통해 답 찾기
		ArrayList<Integer> result = new ArrayList<>();
		result.add(list.get(maxHeightIndex).id);
		for (int i=1; i<n; i++) {
			if (dp[i][maxHeightIndex] > dp[i-1][maxHeightIndex]) {
				result.add(list.get(i).id);
			}
		}
		
		
        // 결과 출력
		System.out.println(result.size());
		for (int i=result.size()-1; i>=0; i--) {
			System.out.println(result.get(i));
		}
	}

}

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

📝 문제 풀이 방법

패스트 캠퍼스의 나동빈 강사님의 문제풀이 순서는 다음과 같다.
1. 벽돌을 무게 기준으로 오름차순으로 정렬한다. (무게, 너비, 높이가 0인 벽돌도 추가한다.)
2. N+1크기의 1차원 배열을 만들고 0으로 초기화한 후 임의로 만든 무게 0의 벽돌을 넣어준다.
3. 반복문을 돌며 기존 벽돌에 다음 벽돌을 넣을 수 있는지 확인 후 넣을 수 있다면 기존의 높이+현재 넣은 벽돌의 높이로 값을 업데이트해준다.
3-1. 이전 벽돌 위에 쌓을 수 없다면 그 이전에 쌓은 벽돌과 비교하여 올릴 수 있는 벽돌 위에 벽돌을 올린 값으로 업데이트 해준다.
4. 최종 배열에서 가장 높이가 높은 index를 찾아내고 역으로 벽돌의 높이를 빼가며 쌓인 벽돌들을 알아낸다.

이미지 출처: Fast Campas - 한번에 끝내는 Java/Spring 웹 개발 마스터 초격차 패키지 Online.

👨🏻‍💻 패캠 코드 참조하여 작성한 코드 (통과)

package baekjoon;

import java.io.*;
import java.util.*;

public class B2655 {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		ArrayList<Brick> list = new ArrayList<>();
		list.add(new Brick(0,0,0,0));
		for (int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int area = Integer.parseInt(st.nextToken());
			int height = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			list.add(new Brick(i+1, area, height, weight));
		}
		
        	// 넓이 기준으로 정렬하기
		Collections.sort(list);
		
		int[] dp = new int[n+1];
		
		for (int i=1; i<=n; i++) {
			for (int j=0; j<i; j++) {
				if (list.get(i).area > list.get(j).area)
					dp[i] = Math.max(dp[i], dp[j]+list.get(i).height);
			}
		}
		
		int maxHeight = -1;
		
		for (int i=0; i<=n; i++) {
			if (maxHeight < dp[i]) maxHeight = dp[i];
		}
		
		int index = n;
		ArrayList<Integer> result = new ArrayList<>();
		
		while (index!=0) {
			if (maxHeight == dp[index]) {
				result.add(list.get(index).id);
				maxHeight -= list.get(index).height;
			}
			index--;
		}
		
		System.out.println(result.size());
		for (int i=result.size()-1; i>=0; i--) {
			System.out.println(result.get(i));
		}
	}
}

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