[인프런] 가장 높은 탑 쌓기

---

문제설명

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

• 조건1 : 벽돌은 회전시킬 수 없다. 즉, 옆면(높이)을 밑면으로 사용할 수 없다.
• 조건2 : 밑면의 넓이가 같은 벽돌은 없으며, 무게도 같은 벽돌은 없다.
• 조건3 : 벽돌들의 높이는 같을 수도 있다.
• 조건4 : 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
• 조건5 : 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

입력조건

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

출력조건

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

사고과정

• 증가하는 부분 수열 최대 길이를 구하는 문제임은 파악했다. 그런데 주어진 벽돌을 그대로 사용하지 않아도 되는 것을 파악한 후 벽돌을 나열하는 모든 경우의 수를 DFS로 탐색한 후 LIS 알고리즘을 사용하기 위해 구현했다. 하지만 DFS로 탐색하는 게 시간이 너무 오래걸려 시간 초과가 발생했다..
• 그래서 힌트를 보았는데, 애초에 원초적으로 가장 높은 길이의 탑을 쌓는 것이기 때문에 가장 앞에오는 벽돌을 밑면 또는 무게가 가장 무거운 것들부터 내림차순으로 정렬하면 되었다..! 이를 놓쳤다.. ㅜㅜ 정렬하게 되면 벽돌이 주어지는 한 경우에 대해서만 LIS 알고리즘을 사용하면 되었다. 아쉽드아..
• 힌트를 보고 스스로 구현했을 때, LIS 알고리즘을 사용할 때 밑면, 무게 모두 비교하면서 했지만 애초에 밑면 또는 무게로 정렬하게 되면 정렬시킨 기준은 비교할 필요 없었다.. 어차피 정렬되어있으니 모두 이미 다 앞의 벽돌들이 모두 크기 때문!

풀이(스스로 못 푼 풀이)

- 강의 풀이

n = int(input())
arr = []  # 밑면 넓이, 높이, 무게 넣기
for _ in range(n):
    width, height, weight = map(int, input().split())
    arr.append((width, height, weight))
arr.sort(reverse=True)  # 넓이 큰 순으로 정렬
dp = []
for _, h, _ in arr:
    dp.append(h)

answer = 0
for i in range(1, n):
    for j in range(i-1, -1, -1):
        if arr[j][2] > arr[i][2]:
            dp[i] = max(dp[i], dp[j] + arr[i][1])
    answer = max(answer, dp[i])
print(answer)

- 나의 풀이

n = int(input())
arr = []  # 밑면 넓이, 높이, 무게 넣기
for _ in range(n):
    width, height, weight = map(int, input().split())
    arr.append((width, height, weight))
# 넓이(또는 무게)가 큰 순서대로 정렬 -> 이걸 놓쳐부렸네...
arr.sort(key=lambda x: (-x[0]))
dp = []
for _, h, _ in arr:
    dp.append(h)

answer = 0
for i in range(1, n):
    for j in range(i-1, -1, -1):
        if arr[j][0] > arr[i][0] and arr[j][2] > arr[i][2]:
            dp[i] = max(dp[i], dp[j] + arr[i][1])
    answer = max(answer, dp[i])
print(answer)