[BaekJoon]2655が一番高いタワー(Java)

🔗 質問リンク

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

📝 解題方法

最初に解く方法は以下の通りです.
1.レンガの幅を基準に降順に並べる.
2.Nブロックレンガを動的に操作するために、NxNの配列を作成する.
3.2つのloopで各レンガに既製レンガがあるかどうかをチェックし、レンガを付けることができる場合は、以前の高さに既製レンガの高さを加えます.
4.最後の配列で値の最大値を探し、その列を逆方向に追跡し、高さが変化したときのレンガ(積み上げられたレンガ)を見つけます.
※現在のレンガは各列にあるレンガを指し、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サイズの一次元配列を作成し、0に初期化して任意重量0のレンガを入れる.
3.既存のレンガに次のレンガを入れることができるかどうかを繰り返しチェックし、入れることができれば、値を既存の高さ+現在のレンガを入れる高さに更新することができます.
3-1. 前のタイルに積み上げることができない場合は、前のタイルに積み上げることができる値にレンガを更新することができます.
4.最終配列で最も高いindexを見つけ、逆にレンガの高さを取り除き、積み上げられたレンガを見つける.

画像ソース:Fast Campas-JavaとSpring Web開発のプライマリ・ハイパー・パケットのオンライン化を一度に完了します。

👨🏻‍💻 参照カードカムコード作成コード(通過)

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;
	}
}