1. 문제

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

1-1) 입력설명

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

1-2) 출력설명

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

1-3) 입력예제

5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

1-4) 출력예제

10

2. 코드

import sys
sys.stdin=open("in1.txt", "r")

n = int(input())
stone = []
dy = [0 for _ in range(n+1)]
for i in range(n):
    a, b, c = map(int, input().split())
    stone.append((a, b, c))
stone.sort(reverse=True)
stone.insert(0, 0)
dy[1] = stone[1][1]
res = 0
for i in range(2, n+1):
    max = 0
    for j in range(i-1, 0, -1):
        if stone[j][2] > stone[i][2] and max < dy[j]:
            max = dy[j]
        dy[i] = max + stone[i][1]
    if res < dy[i]:
        res = dy[i]

print(res)

2-2) 변수 설명

dy: 각 인덱스가 마지막(맨 위에 있는 벽돌)이라고 했을 때의 최대 높이를 저장한 리스트

3. 설명

시작하기 앞서 인덱스 번호를 1부터 시작하기 위해 dy와 stone 리스트 모두 0번 인덱스에 0을 insert했다.
벽돌 위에 벽돌을 쌓기 위한 조건은 두 가지가 있다. 아래 있는 벽돌의 1) 밑면이 더 넓어야 하고, 2) 무거워야 한다.
그래서 둘 중 하나의 조건을 미리 만족시키기 위해 stone리스트를 밑면 기준으로 정렬 내림차순으로 정렬을 한다.
이후 dy[1]에는 stone에 맨 앞에 있는 튜플에서 높이(인덱스 1번) 값을 저장한다. 이유: 벽돌 하나를 쌓을 때의 경우의 수는 하나이고 아무 제약이 없기 때문
이후 인덱스 2부터 반복문이 진행된다. 그 안에 있는 for문은 현재 인덱스(i) 기준으로 아래 있는 인덱스를 탐색한다. 이때 j에 있는 값(무게) 가 i보다 커야 하고, 그 중에서 높이가 최대인 값을 구해 dy[i]에 저장해주면 된다.
이 후 res값을 계속해서 초기화해 출력하면 끝난다.

자료: 인프런 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 김태원