BOJ_2655 가장높은탑쌓기

import sys
input = sys.stdin.readline

B = []
for i in range(int(input())):
    B.append((i + 1, *map(int, input().split())))
# 블록을 무게에 대해 내림차순으로 정렬한다.
B.sort(key=lambda x: x[-1], reverse=True)

T = []
for bn, ba, bh, _ in B:
    # 높이의 초깃값으로 받아온 블록의 높이를 지정한다.
    h_max = bh
    # 쌓은 블록 번호는 초깃값을 빈 리스트로 지정한다.
    # 지금까지 쌓은 블록 번호에 현재 블록의 번호를 추가할 예정으로
    # 처음에 쌓인 블록은 없기 때문에 빈 리스트다.
    n_max = []
    # 현재 만든 탑을 순회하면서 각 높이, 최소밑면, 쌓은 블록 번호에 대해
    for th, ta, tns in T:
        # 탑의 최소 밑면이 블록의 밑면보다 크고 
        # 탑을 쌓았을 때 높이가 최대 탑 높이보다 높으면
        if ta > ba and bh + th > h_max:
            # 최대 탑 높이를 바꾸고
            h_max = bh + th
            # 쌓은 블록 번호를 해당 탑의 쌓은 블록 번호로 바꾼다.
            n_max = tns[:]
    # 쌓은 블록 번호에 현재 쌓은 블록의 번호를 추가하고
    n_max.append(bn)
    # 최대 높이, 현재 블록의 밑면과 함께 탑으로 추가한다.
    T.append((h_max, ba, n_max))

# 최대 높이인 탑의 쌓은 블록 번호를 가져온다.
res = max(T)[-1]
print(len(res))
print("\n".join(map(str, res[::-1])))

B = sorted(
    [list(map(int, input().split())) + [i + 1] for i in range(int(input()))],
    reverse=True,
)

I = [[b[3]] for b in B]
H = [0 for _ in range(101)]

for i in range(len(B)):
    # H의 초깃값을 해당 블록의 높이로 지정한다.
    H[i] = B[i][1]
    # 현재 블록(i)의 이전 블록(j)들에 대해
    # (현재 블록보다 무게가 큰 블록)
    for j in range(i):
        # j번째 블록의 밑면이 i번째보다 크고
        # i번째 탑의 높이보다 j번째 탑의 높이에 i번째 블록의 높이를 합한 것이 더 크면
        if B[i][2] < B[j][2] and H[i] < H[j] + B[i][1]:
            # i번째 탑의 높이를 
            # j번째 탑의 높이에 i번째 블록의 높이를 더한 값으로 바꾸고.
            H[i] = H[j] + B[i][1]
            # i번째 탑의 블록 목록을
            # j번째 탑의 블록 목록에 i번째 블록을 추가한 것으로 바꾼다.
            I[i] = [B[i][3]] + I[j]

# 최대 높이를 갖는 탑의 블록 목록을 가져온다.
res = I[H.index(max(H))]
print(len(res))
[print(i) for i in res]

import sys
input = sys.stdin.readline

N = int(input())
B = [(0, 0, 0, 0)]
for i in range(1, N + 1):
    B.append((i, *map(int, input().split())))
# 블록을 무게에 대해 오름차순으로 정렬한다.
B.sort(key=lambda x: x[3])

# 탑의 높이를 담을 리스트
H = [0] * (N + 1)

# 각 블록을 순회하면서
for i in range(1, N + 1):
    # 빈 블록부터 해당 블록의 이전 블록들에 대해
    # (현재 블록보다 가벼운 블록)
    for j in range(0, i):
        # i번째 블록의 밑면이 j번째 블록보다 크면
        if B[i][1] > B[j][1]:
            # i번째 탑의 높이를
            # i번째 탑의 높이와 j번째 탑의 높이에 i번째 블록의 높이를 합한 것 중
            # 더 큰 값으로 지정한다.
            H[i] = max(H[i], H[j] + B[i][2])

# 탑의 최대 높이를 구하고
max_h = max(H)
# 그 탑의 번호를 구한 뒤
idx = H.index(max_h)
result = []

# 최대 높이 탑의 이전 탑들을 순회하면서
while idx != 0:
    # 해당 탑의 높이가 최댓값과 같으면
    if max_h == H[idx]:
        # 결과 리스트에 블록의 번호를 추가하고
        result.append(B[idx][0])
        # 최대 높이를 그 값에서 해당 블록의 높이를 뺀 값으로 바꾼다. 
        max_h -= B[idx][2]
    idx -= 1

print(len(result))
[print(i) for i in result[::-1]]