[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 6

가장 높은 탑 쌓기

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.
(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
(조건3) 벽돌들의 높이는 같을 수도 있다.
(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

▣ 입력설명
입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터연속적인 번호를 가진다.

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

▣ 입력예제 1
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

▣ 출력예제 1
10

import sys
# sys.stdin = open("input.text", "rt")

#가장 높은 탑 쌓기
#밑면 넓이, 벽돌 무게가 조건
#위로 갈수록 넓이 좁고 무게 가벼워야 한다

n = int(input())
data = []
for _ in range(n):
    a,b,c = map(int, input().split()) #밑면 넓이, 벽돌 높이, 무게
    data.append((a,b,c))

data.sort() #밑면 넓이로 오름차순 -> 조건 하나 제외
#이제 벽돌 무게만 뒤로 갈수록 증가. 즉 최장 부분 증가수열!
dp = [0] * n #각 인덱스 값까지의 최대 세울 수 있는 개수 
dp[0] = data[0][1]

for i in range(1,n):
    h = 0
    for j in range(i):
        if data[j][2] < data[i][2] and dp[j] > h:
            h = dp[j] #이전까지의 최장높이를 저장해놓음
    dp[i] = h + data[i][1]

print(max(dp))

👻 코멘트

문제 유형을 먼저 파악하는게 중요하다. 두 조건이 존재했고, 먼저 하나의 조건을 오름차순으로 정렬한 뒤 나머지 하나를 가지고 판단했어야 했는데 위로 갈수록 무게가 작아야 한다. 그렇기에 최장 부분 증가수열. 즉 올라갈수록 값이 커지거나 작아지거나 근데 그 개수가 최대가 되도록.

• 이런 유형의 문제는 dp의 최장 부분 증가수열 형식으로 문제를 해결할 수 있다.