[알고리즘 문제풀이] 가장 높은 탑 쌓기

문제 제목 : 가장 높은 탑 쌓기

문제 난이도 : 상

문제 유형 : 동적 프로그래밍, LIS, 다이나믹 프로그래밍

https://www.acmicpc.net/problem/2655
시간 제한 : 1초
메모리 제한 : 128MB

문제풀이 아이디어

< 소스코드 >

n = int(input())
array = []

array.append((0, 0, 0, 0))
for i in range(1, n + 1):
    area, height, weight = map(int, input().split())
    array.append((i, area, height, weight))

# 무게를 기준으로 정렬
array.sort(key=lambda data: data[3])

dp = [0] * (n + 1)

for i in range(1, n + 1):
    for j in range(0, i):
        if array[i][1] > array[j][1]:
            dp[i] = max(dp[i], dp[j] + array[i][2])

max_value = max(dp)
index = n
result = []

while index != 0:
    if max_value == dp[index]:
        result.append(array[index][0])
        max_value -= array[index][2]
    index -= 1

result.reverse()
print(len(result))
[print(i) for i in result]