[알고리즘] 가장 높은 탑 쌓기

(문제) 가장 높은 탑 쌓기

---

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다.

탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

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

입력설명

입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다.

입력으로 주어지는 벽돌의 수는 최대 100개이다.

둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다.

각 벽돌은 입력되는 순서대로 1부터연속적인 번호를 가진다.

출력설명

첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.

테스트케이스

입력예제	출력예제
5 25 3 4 4 4 6 9 2 3 16 2 5 1 5 2	10
5 14 5 18 19 10 5 7 12 14 5 6 19 8 13 7	18
10 114 96 290 65 74 201 261 19 105 181 60 275 90 145 254 286 118 64 16 24 205 288 128 299 96 36 74 182 5 35	443

---

해결방법

blocks 형태 [[25, 3, 4], ... ]
blocks[?][0] = 밑면 넓이
blocks[?][1] = 밑면 높이
blocks[?][2] = 밑면 무게

벽돌의 가장 큰 높이를 구하는 것이기 때문에 무게 기준 혹은 밑면 넓이 기준으로 정렬 시켜서 한다.

조건 :
밑면의 넗이가 大 -> 小 만 쌓을 수 있다
무게가 大 -> 小 만 쌓을 수 있다.

다이나믹 프로그래밍을 이용할 것이기 때문에 dt라는 다이나믹 테이블을 생성하여, 각 블럭마다 가장 큰 높이 값을 해당 dt 인덱스에 저장할 것이다.

처음 하나는 무조건 쌓을 수 있기 때문에 자기 자신 높이를 dt[0] 에 저장

현재와 이전 것들 모든 것과 비교하여 밑변 넗이는 이미 정렬하여 조건에서 빼고, 현재 무게가 이전 무게보다 가벼워야한다.

조건을 만족하면 만족하는 인덱스를 기준으로 dt의 인덱스에 있는 값을 다른 것과 비교해서 얻은 모든 높이의 최대값과 비교하여 가장 큰 것을 찾아낸다.

찾아낸 큰 높이 값과 현재 자신의 높이 값을 더한 후, dt 자신의 위치에 높이를 저장한다.

이 과정을 계속 반복한다.

---

코드

n = int(input())

# blocks 형태 [[25, 3, 4], ]
# blocks[?][0] = 밑면 넓이
# blocks[?][1] = 밑면 높이
# blocks[?][2] = 밑면 무게
blocks = [list(map(int, input().split())) for _ in range(n)]

# 벽돌은 순서가 없어서 무게 기준 혹은 밑면 기준으로 정렬 시켜서 한다.
blocks = sorted(blocks, reverse=True, key=lambda x:x[0])

# 조건 :
# 밑면의 넗이가 大 -> 小 만 쌓을 수 있다
# 무게가 大 -> 小 만 쌓을 수 있다.

dt = [0] * n

# 하나는 무조건 쌓을 수 있기 때문에 자기 자신 높이 저장
dt[0] = blocks[0][1]


for i in range(1, n):
    # 최대 값
    _max = 0 
    for j in range(i-1, -1, -1):
        # 현재와 이전 것을 비교
        # 현재 보다 큰 것이 나와야 한다 (무게)
        # 넓이는 이미 위에서 정렬 시켰으니 조건으로 걸 필요가 없다
        if blocks[j][2] > blocks[i][2]:
            # 다이나믹 테이블에 저장 되어있는 높은 높이를 찾는다.
            if _max < dt[j]:
                _max = dt[j]

    # 찾은 높이와 현재 자신을 높이를 더해서 저장한다
    dt[i] = _max + blocks[i][1]

print(max(dt))