[알고리즘][X] 가장높은탑쌓기

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

2655번: 가장높은탑쌓기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static class Brick {
		int id;
		int area;
		int height;
		int weight;
		public Brick(int id, int area, int height, int weight) {
			super();
			this.id = id;
			this.area = area;
			this.height = height;
			this.weight = weight;
		}
		
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		Brick[] bricks = new Brick[N+1];
		bricks[0] = new Brick(0, 0, 0, 0);
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int area = Integer.parseInt(st.nextToken());
			int height = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			bricks[i] = new Brick(i, area, height, weight);
		}
		
		Arrays.sort(bricks, new Comparator<Brick>() {

			@Override
			public int compare(Brick o1, Brick o2) {
				return o1.area - o2.area;
			}
		});
		
		int[] dp = new int[N+1];
		for (int i = 1; i <= N; i++) {
			dp[i] = bricks[i].height;
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j < i; j++) {
				Brick brick = bricks[i];
				if (brick.weight >= bricks[j].weight) {
					dp[i] = Math.max(dp[i], dp[j] + brick.height);
				}
			}
		}
		
		int maxHeight = Integer.MIN_VALUE;
		for (int i = 0; i <= N; i++) {
			maxHeight = Math.max(maxHeight, dp[i]);
		}
		
		StringBuilder sb = new StringBuilder();
		
		List<Integer> result = new ArrayList<>();
		int count = 0;
		int index = N;
		while (index > 0) {
			if (maxHeight == dp[index]) {
//				sb.append(bricks[index].id).append("\n");
				result.add(bricks[index].id);
				maxHeight -= bricks[index].height;
				count++;
			}
			index--;
		}
		
//		sb.reverse();
//		sb.insert(0, count);
		
//		System.out.println(sb);
		System.out.println(result.size());
		for (int i=result.size()-1; i>=0; i--) {
			System.out.println(result.get(i));
		}
	}
}

나의 풀이

- 처음에 주석이 되어 있는 sb.reverse를 이용해서 풀었는데 틀렸다. 왜 그럴까?

- 두자릿수 이상이면 문자열이기 때문에 아예 reverse가 된다. 예를 들어, 21이 12가 된다.