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

1. 생각정리

• 탑을 쌓을 때 고려해야 하는 사항은 세 개다.
  • 무거운 것은 무조건 아래
  • 밑면이 넓은 것은 무조건 아래
  • 위의 두 조건들을 만족시키면서 가장 높은 탑을 쌓을 수 있어야 함
• 일단 '밑면의 넓이' 혹은 '무게' 중 하나에 대해 정렬을 해준 뒤 코드를 짜면 생각해야 할 조건이 하나 줄어든다.
• 그리고 dp를 이용해서 하나씩 영역을 확장시키며 쌓을 수 있는 가장 높은 높이를 구할 수 있지 않을까?

주어진 벽돌 정보 mapp

무게를 기준으로 정렬한 벽돌 정보 mapp

• 여기서 "첫 번째까지 고려한 최대 높이는 dp [1]에", "두 번째까지 고려한 최대 높이는 dp [2]에"... 이렇게 dp를 채운 뒤
• dp리스트의 최댓값이 쌓을 수 있는 최대 높이이다.
• 그리고 mapp과 dp를 바탕으로 하나씩 기억을 더듬어가면 문제가 원하는 답을 도출할 수 있다.

 

2. 성공 코드

N = int(input())
mapp = []
mapp.append((1,1,1,1))
for i in range(1,N+1):
    a,b,c = map(int, input().split()) #(넓이, 높이, 무게) 순서
    mapp.append((i,a,b,c))

#dp
dp = [0]*(N+1)
#무게 순으로 일단 정렬
mapp.sort(key = lambda x: x[3])

#mapp를 훑으면서 dp를 갱신
for i in range(1,N+1):
    for j in range(0,i):
        if mapp[i][1]>mapp[j][1]: #현재 넓이가 훑으며 거쳐온 이전 넓이보다 클 때
            dp[i] = max(dp[i], dp[j]+mapp[i][2])
            
#가장 높이 쌓을 수 있는 높이 찾기
max_height = max(dp)

#기억을 더듬으며 백 트래킹
index = N
history = []

while index!=0:
    if dp[index]==max_height:
        history.append(mapp[index][0])
        max_height-=mapp[index][2]
    index-=1
    
print(len(history))
history.reverse()
for i in history:
    print(i)

###

마지막에

history.sort(reverse=True) 하면 틀리고

history.reverse() 하면 맞더라고요