Part7.6_동적프로그래밍(DynamicProgramming)_가장 높은 탑 쌓기

문제

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

가장 높은 탑을 구하는 프로그램 만들자

입력

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

출력

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

풀이

• 튜플로 넓이, 높이, 무게값 저장
• 내림차순 정렬하고 i가 끝이라고 생각하고
• j 값과 비교하며 max 값을 새로운 배열에 누적한다.
• 이후 max(배열) 로 최댓값을 출력한다.

코드

import sys
def input():
    return sys.stdin.readline().rstrip()

N = int(input())
top = []
res = [0] * (N)
for i in range(N):
    x, y, z = map(int,input().split())
    top.append((x,y,z))
top.sort(key=lambda x: -x[0])

res[0] = top[0][1]

for i in range(1,N):
    maxZ = 0

    for j in range(i-1,-1,-1):
        if top[i][2] < top[j][2] and maxZ < res[j]:
            maxZ = res[j]
    res[i]+=top[i][1]+maxZ
print(max(res))    

정답 코드 비교

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

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
briks=[]
for i in range(N):
    a,b,c = map(int,input().split())
    briks.append((a,b,c))
briks.sort(reverse=True)

dy=[0]*N
dy[0] = briks[0][1]
res = briks[0][1]

for i in range(1,N):
    max_h = 0
    for j in range(i-1,-1,-1):
        if briks[j][2] > briks[i][2] and dy[j]>max_h:
            max_h=dy[j]
    dy[i] = max_h+briks[i][1]
    res = max(res, dy[i])
print(res)

코멘트

아 튜플 인덱스 0 으로 정렬할때는 굳이 lambda 안쓰고 sort 해도 되는구나