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

문제

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

[해설코드]

if __name__=="__main__":
	n=int(input())
    bricks=[]
    for i in range(n):
    	a,b,c=map(int,input().split())
        bricks.append((a,b,c))
    bricks.sort(reverse=True)
    dy=[0]*n
    dy[0]=bricks[0][1] #0번 벽돌의 높이
    res=bricks[0][1] 
    for i in range(1,n):
    	max_h=0
        #i번째 벽돌=만들고자 하는 탑의 가장 상단 벽돌
        #i번쨰 아래에 있는 벽돌들 : j
        for j in range(i-1,-1,-1): 
        	#dy[j]>max_h는 벽돌들 중에 가장 길이가 긴 값을 찾는 로직
        	if bricks[j][2]>bricks[i][2] and dy[j]>max_h:
            	max_h=dy[j]
        dy[i]=max_h+bricks[i][1]
        res=max(res,dy[i])
    print(res)

1.dp테이블은 해당 인덱스의 벽돌을 최상단에 위치시켰을 때의 최대길이
2. 벽돌을 배치할 때 나는 밑에서부터 벽돌을 쌓는 알고리즘으로 생각했다.(즉, 배열을 내림차순 정렬 후 원소들을 하나씩 순회하면서 조건을 만족하는 벽돌의 길이를 dp에 추가)<-틀린 알고리즘
3. dp테이블의 기준을 각 원소들이 탑의 최상단에 왔을 때를 기준으로 조건을 만족하면 이전의 dp배열의 원소 중 가장 큰 값에서 현재원소의 높이를 더한다.

2.dp테이블

index	0	1	2	3	4
	3	2	5	4	10