[백준] 가장 높은 탑 쌓기.py

import sys
N = int(sys.stdin.readline())
arr = [(0,0,0,0)]
for i in range(1, N+1):
    area, height, weight = map(int, sys.stdin.readline().split())
    arr.append((i, area, height, weight))
arr.sort(key = lambda x: x[3])

# table[i] = i번 벽돌을 가장 아래에 두었을 때 최대 높이. (무게 순으로 정렬된 상태에서)
# table[i] = max(table[i], table[j] + height[i]) if area[i] > area[j]
table = [0] * (N+1)

for i in range(1, N+1):
    for j in range(0, i):
        # area가 더 큰 경우
        if arr[i][1] > arr[j][1]:
            table[i] = max(table[i], table[j] + arr[i][2])

max_height = max(table)
idx = table.index(max_height)
result = []

# table height를 토대로 벽돌의 index 역산하기.
while idx != 0:
    if max_height == table[idx]:
        result.append(arr[idx][0])
        max_height -= arr[idx][2]
    idx -= 1
print(len(result))
[print(i) for i in result[::-1]]