[BOJ] 가장 높은 탑 쌓기 #2655

가장 높은 탑 쌓기 #2655

• https://www.acmicpc.net/problem/2655
• 난이도: 상
• 알고리즘: 동적 프로그래밍

문제

• 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

1. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
2. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
3. 벽돌들의 높이는 같을 수도 있다.
4. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
5. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

입력

• 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.

출력

• 탑을 쌓을 때 사용된 벽돌의 수를 빈칸없이 출력하고, 두 번째 줄부터는 탑의 가장 위 벽돌부터 가장 아래 벽돌까지 차례로 한 줄에 하나씩 벽돌 번호를 빈칸없이 출력한다.

입력 예제

5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

출력 예제

3
5
3
1

문제 풀이 핵심 아이디어

• 가장 긴 증가하는 부분 수열(LIS) 문제의 심화 변형 문제입니다.
• 벽돌의 수가 N개일 때, 시간 복잡도 $O(N^2)$ 으로 해결할 수 있습니다.
• 벽돌의 번호를 출력해야 한다는 점에서, 계산된 테이블을 역추적할 수 있어야 합니다.
• 가장 먼저 벽돌을 무게 기준으로 정렬합니다.
• D[i] = 인덱스가 i인 벽돌을 가장 아래에 두었을 때의 높이
• 각 벽돌에 대해서 확인하며 D[i]를 갱신합니다.
• 모든 0 ≤ j < i 에 대하여, D[i] = max(D[i], D[j] + height[i]) if area[i] > area[j]

나의 소스코드

n = int(input())
bricks = [(0, 0, 0, 0)]

for idx in range(1, n + 1):
    a, h, w = map(int, input().split())
    bricks.append((idx, a, h, w))
    
bricks.sort(key = lambda x: x[3])

dp = [0] * (n + 1)
for i in range(1, n + 1):
    for j in range(0, i):
        if bricks[i][1] > bricks[j][1]:
            dp[i] = max(dp[i], dp[j] + bricks[i][2])
            
max_value = max(dp)
idx = n
result = []

while idx > 0:
    if max_value == dp[idx]:
        result.append(bricks[idx][0])
        max_value -= bricks[idx][2]
    idx -=1
    
result.reverse()
print(len(result))
for r in result:
    print(r)