Algorithm - 가장 높은 탑 쌓기(LIS 응용)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

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

 

밑면이 정사각형인 직육면체 벽돌을 사용하여 탑을 쌓고자 한다. 

탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

 

(조건 1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.

(조건 2) 밑면의 넓이가 같은 벽돌은 없으며, 무게가 같은 벽돌도 없다.

(조건 3) 벽돌들의 높이는 같을 수 있다.

(조건 4) 탑을 쌓을 때, 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌을 놓을 수 없다.

(조건 5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

 

 

*입력 설명

첫 번째 줄에는 입력될 벽돌의 수가 주어진다.

입력으로 주어지는 벽돌의 수는 최대 100개이다.

두 번째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌의 밑면의 넓이, 높이 그리고 무게가 차례대로 주어진다.

단, 벽돌의 밑면 넓이와 높이 그리고 무게는 모두 양의 정수이다.

각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다.

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_78.txt', 'rt')

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]
    res = bricks[0][1]
    for i in range(1, n):
        max_h = 0
        for j in range(i-1, -1, -1):
            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) 
    
# 출력 : 10

 

input_78.txt(입력)

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

 

 

중요내용

1. 해당 문제에서 벽돌을 쌓을 때, 중요하게 고려해야 할 점은 벽돌의 밑면 넓이와 무게이다.
2. 우선 밑면의 넓이를 기준삼아 내림차순으로 벽돌을 정렬시키고, 해당 순서대로 벽돌을 쌓는다고 가정하면 두 가지 조건(밑면 넓이와 무게) 중에서 밑면의 넓이는 더 이상 고려하지 않아도 된다.
3. 즉, 무게 조건만 고려하여 벽돌을 쌓는 경우의 수만 생각하면 된다.
4. 이 때, 무게 조건을 고려하는 과정에서 LIS의 개념을 활용하면 된다.
5. 참고로, bricks.sort(reverse=True) 코드는 튜플 자료형을 내림차순으로 정렬시키는 코드이다.
6. 튜플 자료형은 우선적으로 맨 앞의 요소를 기준으로 정렬이 되며, 해당 요소 값이 동일하여 정렬을 시키지 못할 경우에는 그 다음 요소를 기준으로 정렬된다.
7. bricks[i] 는 쌓고자 하는 탑의 제일 상단 벽돌을 의미한다.
8. dy[i] 는 쌓고자 하는 탑의 제일 상단에 bricks[i] 벽돌을 놓았을 때, 구할 수 있는 최대 높이를 의미한다.
9. 참고로 리스트 dy에는 쌓을 수 있는 탑의 최대 높이값을 저장한다.
10. dy[0] 값은 항상 bricks[0]의 높이 값이 된다. (즉, dy[0] == bricks[0][1])
11. 변수 max_h에는 bricks[0]부터 bricks[j]까지의 벽돌을 사용하여 쌓을 수 있는 탑의 최대 높이를 저장한다.
    (단, j = i-1)
12. 그 결과, dy[i] = max_h + bricks[i][1] 식이 성립되는 것이다.