DP-가장 높은 탑 쌓기

가장 높은 탑 쌓기
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래
에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프
로그램을 작성하시오. 
(조건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

 

 

n=int(input())

brick=[] # 벽돌을 담자

for i in range(n):
    brick.append(list(map(int,input().split()))) # 밑면 높이 무게

brick.sort(key=lambda x:-x[0]) # 벽돌의 무게가 높은거부터 차례대로 출력시키자

dp=[0]*(n+1)  # 하는하는 탑의 위치의 높이를 저장한다.

res=brick[0][1]
dp[0]=brick[0][1]

print(brick)
for i in range(1,n): # 맨밑은 우리가 위치를 dp 에 저장해놨으니 dp[1]번 부터 차례대로 비교를해보자
    max_height=0
    for j in range(i-1,-1,-1):
        if brick[j][2]>brick[i][2] and max_height<dp[j]: ## 밑에있는벽돌이 더 무거워야하며, 제일높은 높이를 구해야한다.
            
            max_height=dp[j] # 밑에있는 벽돌이 더 무겁고 제일높은 높이를 가진 max_height가 만들어진다.
    print(max_height)

    dp[i]=max_height+brick[i][1]# dp[i]에 높이를 저장해주고
    res=max(dp[i],res) # 원래있던 높이랑 dp[i]비교하여 가장높은 무게를 가진 res 를 출력한다.


print(dp)
print(res)

문제해설:

i=1 일경우

 

현재 위치보다 아래인 j=0의 무게가 더 크니까 max_height(0)+현재블록높이를 구한다.

dp[0]=3 birck[0][1] 으로 초기화를 해주었다.

dp[1]=2가 담기게된다.

 

i=2 일경우

j=0 과 ,j=1 둘다 무게가 현재블록보다 무겁다! 그럼 조건하나는 일치 ! max_height는 0으로 계속 초기화되니까

max_h 에 가장 큰 dp값을 담게되는것이 그럼 dp[0]과 dp[1]중 가장 큰 3+ 현재 블록높이를 더해주면 5가된다

dp[2]=5 가 된다

 

다음과 같은 로직을 반복하게 되면

 

답은 :10이 나오게된다.