[김태원 알고리즘] 가장 높은 탑 쌓기 (DP)

사용 언어: Python3

문제

풀이

내 풀이

N = int(input()) # 벽돌 수
lst = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0] * N # ✅ lst[i]가 탑의 맨 꼭대기일 때 최대 높이
dp[0] = lst[0][1] # lst[0]이 탑의 맨 꼭대기일 때 높이는 lst[0][1]

lst.sort(key=lambda x:x[0], reverse=True) # ✅ 밑면 기준 내림차순 정렬 -> 이제 위치 고정

# ✅ 무게만 기준으로 두고 생각
for i in range(1, N):
    mx = 0
    for j in range(i):
        if lst[j][2] > lst[i][2]: # ✅ 나(lst[i])의 무게보다 무거워야 함
            mx = max(mx, dp[j])
    dp[i] = lst[i][1] + mx # ✅ 내 "높이"에 누적 (나보다 무거운 벽돌이 없으면 mx는 0)

print(max(dp))

• 성공!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기