[백준 2655번] 가장높은탑쌓기

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

 

 

해당 문제는 DP + 역추적 문제였다.

 

초기에 해당 문제를 풀 때, 밑면의 넓이도 다르고, 무게도 다르며, 높이는 같을 수 있다는 조건과 함께

피라미드 형태처럼 밑면의 넓이는 위로갈수록 작아지면서, 무게도 작아져야 하는 형태를 가지면서 쌓을 수 있는 가장 높은 길이의 탑 형태를 구하라는 문제의 요지를 파악했다.

 

처음엔 비교 연산자 Comparble을 사용할 때, 밑면과 무게를 동시에 비교할 수는 없기 때문에 밑면의 넓이를 기준으로 정렬하였다.

따라서 문제에서 쌓을 수 있는 가장 높은 길이의 탑의 길이는 구했지만, 이후, 역추적을 통해 해당 탑을 쌓는데 필요했던 벽돌이 무엇인지를 찾는 과정에서 헤매서 다른 블로그를 참고하였다.

 

참고한 블로그

https://velog.io/@seongwon97/BaekJoon-2655-%EA%B0%80%EC%9E%A5%EB%86%92%EC%9D%80%ED%83%91%EC%8C%93%EA%B8%B0-Java

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

 

다음 블로그와 같이 dp 형태로 가장 높은 길이의 idx를 찾은 후에, 해당 인덱스에 해당하는 벽돌의 번호를 저장하고, 해당 벽돌의 높이만큼을 빼주고, 이전 dp를 순회하면서 그때의 높이가 일치하는 벽돌의 번호를 찾아서 결과값을 저장해주었다.

 

		// 내가 해결하지 못했던 부분.
		// TODO: 역순으로 사용했던 벽돌을 찾아야 함.

		int maxHeight = -1;

		for (int i = 1; i < N + 1; i++) {
			if (maxHeight < dp[i])
				maxHeight = dp[i];
		}

		int idx = N;
		List<Integer> res = new ArrayList<>();

		while (idx != 0) {
			if (maxHeight == dp[idx]) {
				res.add(bricks.get(idx).idx);
				maxHeight -= bricks.get(idx).height;
			}
			idx--;
		}

		StringBuilder sb = new StringBuilder();
		sb.append(res.size()).append('\n');

		for (int i = res.size()-1; i >= 0; i--) {
			sb.append(res.get(i)).append('\n');
		}
		System.out.println(sb);

	}

 

내가 실패한 이유

ArrayDeque를 활용하며, 객체를 만들어서 객체안의 List<Integer> 형태를 통해 벽돌의 번호들을 저장하는 과정에서 복잡도가 증가하였고, 그 결과 내가 코드의 어떤 로직이 잘못됐는지 확인하지 못하였다.

 

다음은 전체 코드이다.

 

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

/**
 *packageName    : _250513
 * fileName       : BOJ_G3_2655_가장높은탑쌓기
 * author         : moongi
 * date           : 5/13/25
 * description    :
 *
 * 1. 피라미드 형태로 쌓아야 하며, 무게또한 내림차순으로 쌓아져야 한다.
 */
public class BOJ_G3_2655_가장높은탑쌓기 {
	static class Brick implements Comparable<Brick> {
		int idx;
		int width, height, weight;

		public Brick(int idx, int width, int height, int weight) {
			this.idx = idx;
			this.width = width;
			this.height = height;
			this.weight = weight;
		}

		@Override
		public int compareTo(Brick o) {
			return this.weight - o.weight;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int N = Integer.parseInt(br.readLine());
		List<Brick> bricks = new ArrayList<>();
		bricks.add(new Brick(0, 0, 0, 0));

		int a, b, c;
		for (int i = 1; i < N + 1; i++) {
			st = new StringTokenizer(br.readLine());

			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());

			bricks.add(new Brick(i, a, b, c));

		}

		// 무게 순으로 오름차순 정렬
		Collections.sort(bricks);

		// 해당 벽돌을 넣었을 때, 나올 수 있는 최대의 높이
		int[] dp = new int[N + 1];

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

			for (int j = 0; j < i; j++) {

				// 현재 벽돌의 밑면의 넓이가 더 크다면
				if (bricks.get(i).width > bricks.get(j).width) {
					dp[i] = Math.max(dp[i], dp[j] + bricks.get(i).height);
				}

			}
		}

		// 내가 해결하지 못했던 부분.
		// TODO: 역순으로 사용했던 벽돌을 찾아야 함.

		int maxHeight = -1;

		for (int i = 1; i < N + 1; i++) {
			if (maxHeight < dp[i])
				maxHeight = dp[i];
		}

		int idx = N;
		List<Integer> res = new ArrayList<>();

		while (idx != 0) {
			if (maxHeight == dp[idx]) {
				res.add(bricks.get(idx).idx);
				maxHeight -= bricks.get(idx).height;
			}
			idx--;
		}

		StringBuilder sb = new StringBuilder();
		sb.append(res.size()).append('\n');

		for (int i = res.size()-1; i >= 0; i--) {
			sb.append(res.get(i)).append('\n');
		}
		System.out.println(sb);

	}
}