[ 백준 ] 2655 가장 높은 탑 쌓기 (python)

 

 

www.acmicpc.net/problem/2655

2655번: 가장높은탑쌓기

문제

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

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

입력

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

 

출력

탑을 쌓을 때 사용된 벽돌의 수를 빈칸 없이 출력하고, 두 번째 줄부터는 탑의 가장 위 벽돌부터 가장 아래 벽돌까지 차례로 한 줄에 하나씩 벽돌 번호를 빈칸 없이 출력한다.

 

예제입력 1

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

 

예제출력 1

3
5
3
1

 

문제 풀이

LIS (최장 부분 수열) 문제의 변형된 버전으로 다이나믹 프로그래밍 문제임

 

우선 아래 벽돌이 항상 무거워야 하기 때문에 벽돌을 무게 기준으로 정렬을 해주고,

각 벽돌 마다 D[i]를 갱신해 준다

( D[i]는 인덱스가 i인 벽돌을 가장 아래에 두었을 때 최대 높이 )

 

이 문제의 점화식은

D[i] = max(D[i], D[i] + height[i] ) if area[i] > area[j]

 

 

그림을 통해 좀 더 자세히 알아보자

 

n = 5라고 했을 때, 가장 우선적으로 무게를 기준으로 정렬을 해준다

그리고 테이블을 0으로 초기화시켜준다

 

0번째 벽돌과 비교해서 첫 번째 벽돌이 너비가 더 넓기 때문에 ( 0 < 1 )

첫 번째 벽돌의 높이만큼 +5를 해준다

 

 

두 번째 벽돌이  0번째 벽돌보다 너비가 넓기 때문에 D[2] = D[0] + height[2] = 0 + 2

두 번째 벽돌이 첫 번째 벽돌보다 너비가 넓기 때문에 D[2] = max(D[2],  D[1] + height[2] ) = max( 2, 5 + 2) = 7

 

D[4]의 값이 9인 이유는

0번째 벽돌보다 네 번째 벽돌의 너비가 넓으므로 D[4] = 0 + 2 = 2

첫 번째 벽돌보다 네 번째 벽돌의 너비가 넓으므로 D[4] = max(2, 5 + 2) = 7

두 번째 벽돌보다 네 번째 벽돌의 너비가 넓으므로 D[4] = max(7, 7 + 2) = 9

 

세 번째 벽돌은 네 번째 벽돌보다 너비가 넓으므로 조건X

 

최종적으로 가장 높은 높이는 10이다

 

높이를 구했으면 각각 어떤 벽돌이 사용됐는지 알아야 하기 때문에

가장 높은 높이는 인덱스 3번임, 따라서 최고 높이에서 3번 벽돌의 높이만큼 빼준다 (10 - 3)

그리고 7의 값을 갖는 D배열의 원소를 찾고 인덱스 번호도 찾는다

인덱스 번호를 이용해 위와 같은 방법을 반복해주면서 사용된 벽돌 리스트를 출력해주면 끝!

 

n = int(input())
array = []

array.append((0,0,0,0))

for i in range(1, n + 1):
    area, height, weight = map(int, input().split())
    array.append((i, area, height, weight))
    
# 무게를 중심으로 정렬
array.sort(key=lambda data: data[3])

dp = [0] * (n + 1)

for i in range(1, n + 1):
    for j in range(0, i):
        if array[i][1] > array[j][1]:
            dp[i] = max(dp[i], dp[j] + array[i][2])
            
max_value = max(dp)
index = n
result = []

while index != 0:
    if max_value == dp[index]:
        result.append(array[index][0])
        max_value -= array[index][2]
    
    index -= 1
    
result.reverse()

print(len(result))
[print(i) for i in result]