🔗 문제 링크
📝 문제 설명
문제에서는 회전이 불가능한 직육면체 벽돌들을 이용하여 탑을 쌓는 상황을 다룹니다.
각 벽돌은 밑면 넓이, 높이, 무게 정보를 가지며,
탑을 쌓을 때 아래 조건을 만족해야 합니다:
- 밑면 조건: 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
- 무게 조건: 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
출력은 다음과 같이 구성됩니다:
1. 탑에 사용된 벽돌의 개수 (첫 줄)
2. 탑의 가장 위 벽돌부터 가장 아래 벽돌까지, 각 벽돌의 번호를 한 줄씩 출력
✅ 풀이 접근 방식 및 고민 과정
1. 문제 접근: DP와 백트래킹
-
DP 상태 정의:
dp[i]: i번째 벽돌을 최상으로 했을 때 쌓을 수 있는 탑의 최대 높이
dpBack[i]: i번째 벽돌을 쌓기 직전에 사용한 벽돌의 인덱스 (백트래킹 용) -
전이 조건:
모든 벽돌 j (j < i)에 대해,- if (벽돌 i의 밑면 넓이 > 벽돌 j의 밑면 넓이 and 벽돌 i의 무게 > 벽돌 j의 무게)
- then,
dp[i] = max(dp[i], dp[j] + 벽돌 i의 높이) - 동시에,
dpBack[i] = j
-
정렬 기준 선택:
문제 조건을 만족하기 위해,
넓이(혹은 무게도 가능)에 대해 오름차순 정렬하는 것이 핵심입니다. -
최종 결과 복원:
DP 계산이 완료된 후,
전체 dp 배열에서 최대 높이를 가진 인덱스를 찾아 백트래킹을 통해 탑의 벽돌 번호들을 복원합니다.
2. 내가 겪은 문제: resultIdx 업데이트
초기 코드에서는 내부 반복문에서 dp 값이 갱신될 때마다
dp[i] = dp[j] + bricks.get(i)[1];
dpBack[i] = j;
resultIdx = i;처럼 매번 resultIdx를 i로 업데이트했습니다.
문제점:
이 방식은 i번째 벽돌의 dp 값이 갱신될 때마다 resultIdx가 i로 설정되어,
전체 탑 중 최대 높이를 가진 벽돌의 인덱스를 정확히 추적하지 못합니다.
해결 방법:
각 i에 대한 DP 계산이 끝난 후,
if (maxHeight < dp[i]) { maxHeight = dp[i]; resultIdx = i; }
와 같이 전체 최대 높이와 비교해서 resultIdx를 업데이트해야 합니다.
🔍 최종 코드 구현 (C++ 정답 코드)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N;
private static List<int[]> bricks = new ArrayList<>();
private static int maxHeight;
private static int[] dp;
private static int[] dpBack;
private static int resultIdx;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
bricks.add(new int[]{0, 0, 0});
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int size = Integer.parseInt(st.nextToken());
int height = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
bricks.add(new int[]{size, height, weight, i + 1});
}
dp = new int[N + 1];
dpBack = new int[N + 1];
Collections.sort(bricks, Comparator.comparingInt(o -> o[0]));
// Collections.sort(bricks, Comparator.comparingInt(o -> o[2]));
for (int i = 1; i < N + 1; i++) {
dp[i] = bricks.get(i)[1];
for (int j = 1; j < i; j++) {
if (bricks.get(j)[0] < bricks.get(i)[0] && bricks.get(j)[2] < bricks.get(i)[2]) {
if (dp[i] < dp[j] + bricks.get(i)[1]) {
dp[i] = dp[j] + bricks.get(i)[1];
dpBack[i] = j;
}
}
}
if (maxHeight < dp[i]) {
maxHeight = dp[i];
resultIdx = i;
}
}
// System.out.println(Arrays.toString(dp));
// System.out.println();
// System.out.println(Arrays.toString(dpBack));
// 백트래킹을 이용해서 이전의 벽돌을 참고
Stack<Integer> stack = new Stack<>();
int answer = 0;
while (resultIdx != 0) {
answer++;
stack.add(bricks.get(resultIdx)[3]);
resultIdx = dpBack[resultIdx];
}
stack.add(answer);
while (!stack.isEmpty()) {
sb.append(stack.pop()).append("\n");
}
System.out.println(sb.toString());
}
}
🛠 해결 과정 및 추가 고민
-
DP와 백트래킹 구현:
- 각 벽돌에 대해 dp 값을 계산하고, 이전에 어떤 벽돌을 선택했는지 dpBack 배열을 통해 기록하였습니다.
- 백트래킹 함수
print()를 사용해, 최종 최대 높이 체인을 재귀적으로 출력함으로써
탑의 벽돌 번호를 올바른 순서(가장 위부터 아래)로 복원하였습니다.
-
정렬 기준:
- 넓이에 대해 오름차순 정렬함으로써,
무게 조건 (무게가 가벼운 벽돌 위에 무게가 무거운 벽돌)을 자연스럽게 만족시킬 수 있었습니다.
- 넓이에 대해 오름차순 정렬함으로써,
-
resultIdx 업데이트 문제:
- 초기 코드에서는 DP 전이 시마다 resultIdx를 업데이트해버렸는데,
전체 dp 계산이 끝난 후 최대 높이를 가진 벽돌의 인덱스를 추적하는 방식으로 수정했습니다. - 이 부분이 최적의 탑을 올바르게 복원하는 데 결정적이었습니다.
- 초기 코드에서는 DP 전이 시마다 resultIdx를 업데이트해버렸는데,
✅ 결론
-
DP와 백트래킹 조합:
DP를 이용해 각 벽돌을 최상으로 했을 때의 최대 탑 높이를 계산하고,
백트래킹을 통해 실제 탑의 구성을 복원하는 방법이 효과적이었습니다. -
정렬 기준의 중요성:
문제의 조건을 만족하기 위해 무게 오름차순 정렬을 선택한 것이 핵심이었습니다. -
resultIdx 업데이트:
DP 전이 과정에서 바로 resultIdx를 업데이트하는 대신,
전체 DP 계산 후 최대 높이를 가진 벽돌의 인덱스를 정확하게 추적하는 방법으로 수정하여
올바른 최종 결과를 얻을 수 있었습니다.
