DP 경로 복원

동적계획법 문제 중 최적화 해를 만족하는 경로 까지 복원해야하는 경우,

dp값이 업데이트 될때 아래와 같은 방법이 있다.
(1) parent list를 만들어서 갱신되기 이전 인덱스를 저장하고 마지막에 while문으로 경로 복원
(2) dp 업데이트는 기존대로 수행하고 경로 복원시에 최적화된 해에서 해당 인덱스의 입력값을 빼면서 경로를 복원
(3) path table을 하나 더 만들어서 dp값이 업데이트 될때 path도 같이 업데이트 시켜주는 방식

이중에 (3)이 제일 괜찮은 것 같다.((1), (2) 는 틀리기 쉽다.) 의외로 메모리도 별로 안드는 듯?(왜일까)

관련문제 : [백준] 가장 높은 탑 쌓기

python code

import sys

N = int(sys.stdin.readline())
bricks = [list(map(int, sys.stdin.readline().split()))+[i+1] for i in range(N)]
bricks.sort()
dp = [bricks[i][1] for i in range(N)]
path = [[bricks[i][-1]] for i in range(N)]
for i in range(N):
    for j in range(i):
        if bricks[j][2] < bricks[i][2]:
            if dp[i] < dp[j]+bricks[i][1]:
                dp[i] = dp[j]+bricks[i][1]
                path[i] = path[j] + [bricks[i][-1]]

idx = dp.index(max(dp))
print(len(path[idx]))
[print(a) for a in path[idx]]