2655번: 가장높은탑쌓기 LIS (DP) - Fastcampus

www.acmicpc.net/problem/2655

2655번: 가장높은탑쌓기

# dp[i] = i번째 벽돌을 가장 밑바닥 벽돌로 하는 탑의 최대높이
#         (j번째 벽돌 = i번째 벽돌 위에 올릴수 있는 앞 수열의 더 작고 가벼운 벽돌)
#
#    인덱스,면적,높이,무게
# bricks = [(5,1,5,2),(3,9,2,3),(1,25,3,4),(4,16,2,5),(2,4,4,6)]
#
# dp[1] = {(5,1,5,2)} = 5
# dp[2] = {(5,1,5,2),(3,9,2,3)} = dp[1] + 2 = 7
# dp[3] = {(5,1,5,2),(1,25,3,4)} or {..,(3,9,2,3),(1,25,3,4)} = max(dp[1],dp[2]) + 3 = 10
# dp[4] = max(dp[1],dp[2]) + 2 = 9
# dp[5] = max(dp[1]) + 4 = 9

def run(N, bricks):
    dp = [0] * (N+1)
    bricks = [(0, 0, 0, 0)] + bricks  # dp와 bricks 인덱스 동일하게 맞추기

    for i in range(1, N+1):
        idx, a, h, w = bricks[i]
        for j in range(0, i):  # 앞 수열이면서
            if bricks[j][1] < a:  # 면적이 더 작으면
                dp[i] = max(dp[i], dp[j] + h)

    # 최대높이 10 => 사용된 벽돌 찾기 
    res = []
    i, max_dp = N, max(dp)
    while i > 0:
        if dp[i] == max_dp:
            idx, a, h, w = bricks[i]
            res.append(idx)
            max_dp -= h
        i -= 1
    return list(reversed(res))  # 위 벽돌부터 출력


N = int(input())
bricks = [(i,) + tuple(map(int, input().split())) for i in range(1, N+1)]
bricks.sort(key=lambda x: x[3])  # 무게 순 정렬

ans = run(N, bricks)
print(len(ans))
print("\n".join(map(str, ans)))