[백준/BOJ] gold3 - 2655번 가장높은탑쌓기 (Python)

▶2655 - 가장높은탑쌓기

▶문제

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

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

 

▶입력

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

 

▶출력

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

 

▶예제

 

▶풀이

요즘 들어서 dp만 엄청 푸는 거 같다.

사실 dp 하고 그래프는 알고리즘, 고급 문제 해결 수업시간에 배운 내용들이다.

그래서 그 알고리즘 분류로 계속 풀고 있다.

 

아무튼, 이번 문제도 dp고, 아까 풀었던 플레티넘 문제보다는 조금 쉬웠던 것 같다.

먼저 값들을 입력받고, index값과 함께 arr배열에 저장 후 w순으로 새로 정렬했다.

그 이유는 dp는 bottom-up방식이라서 그것을 무게 순으로 나타내기 위해서 정렬을 새롭게 한 것이다.

 

arr기준으로 dp에 새로운 값을 넣을 것이다.

일단 최대 높이를 구해야 하기 때문에, 자기 index이전에 다른 애들과 비교해서 max값을 구한다.

 

그 max값을 기준으로 max_h를 빼주면서 역으로 result를 구해준다.

if max_h == dp[idx]:
    result.append(arr[idx][0])
    max_h -= arr[idx][2]

이 부분의 코드를 이용하는데, 그 max_h값과 idx에 해당하는 값이 일치하면 idx가 그 순간의 max가 된다.

그래서 idx를 result에 저장해 두고 max_h를 빼준다.

그렇게 반복해서 idx가 0이 되면 while을 종료해준다.

 

출력은 result를 역으로 출력해주면 된다.

n = int(input())
arr = [(0, 0, 0, 0)]

for i in range(n):
    s, h, w = map(int, input().split())
    arr.append((i + 1, s, h, w))
arr.sort(key=lambda x: x[3])
'''
for a in arr:
    print(a)
'''
dp = [0 for i in range(n + 1)]

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

result = []
max_h = max(dp)
idx = dp.index(max_h)
'''
print(max_h)
print(idx)
print(dp)
'''
while True:
    if max_h == dp[idx]:
        result.append(arr[idx][0])
        max_h -= arr[idx][2]
    idx -= 1
    if idx == 0:
        break

print(len(result))
for i in range(len(result)-1, -1, -1):
    print(result[i])

dp는 이전의 값들과 어떤 관계가 있는지 생각해야 한다.

이전에 풀었던 2022.06.23 - [BOJ Code/Platinum] - [백준/BOJ] platinum5 - 1328번 고층 빌딩 (Python)

[백준/BOJ] platinum5 - 1328번 고층 빌딩 (Python)

이 문제 또한 이전 값들과 점화식을 알아내면 쉽게 풀 수 있었던 문제였다.

프로그래밍보다는 수학에 가까웠던 것 같다.

프로그래밍 실력이 수학 실력에 비례한다고는 장담할 수 없지만, 수학을 잘하는 사람에게는 유리한 것 같다.

 

아무튼 한 문제 더 풀면서 4점을 획득했다. 

그동안 해온 것이 많지는 않지만, 적지도 않다. 그래서 그런지 골드 3을 풀어도 4점 오른다...

그래도 플레티넘을 향해서 한발 더 다가간 것 같다.