[Python] 가장 높은 탑 쌓기 (LIS 응용)

문제

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

 

(조건 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())

top = []
weight = []

for i in range(N):
    top.append(list(map(int,input().split())))

    maxi = 0
    
    for t in range(i):
        if top[i][0] <= top[t][0] and top[i][2] <= top[t][2]:
            maxi = max(maxi, top[t][1])
            
    top[i][1]+=maxi

result = 0

for area, height,weight in top:
    result = max(result,height)

print(result)

 

값을 입력받고, 자기 자신보다 무게가 더 나가고 너비가 더 넓은 돌이 있는 경우 가장 큰 높이를 기준으로 앞으로 붙는다.

 

그러다보면, 가장 큰 높이를 가진 값을 출력하면 가장 높이 쌓을 수 있는 탑의 높이를 출력할 수 있다.

 

강사님 코드를 보니 거의 비슷하게 접근하였다.

최대 부분 증가수열 메모...