계단 문제에서 최소 비용이 6이라는 건 구했는데 어느 칸을 밟았는지는 안 남는다. 값을 정할 때 어느 쪽에서 왔는지 같이 적어두면 된다.
def dyna(cur_len):
if cur_len in dp:
return dp[cur_len]
# 값
dp[cur_len] = min(dyna(cur_len - 1), dyna(cur_len - 2)) + stairs[cur_len]
# 경로
if dyna(cur_len - 1) < dyna(cur_len - 2):
path[cur_len] = path[cur_len - 1] + [cur_len]
else:
path[cur_len] = path[cur_len - 2] + [cur_len]
return dp[cur_len]
path = [[]] * (length + 1)
dyna(length)
print(path[length][:-1])
min 으로 값을 정한 뒤, 같은 비교를 한 번 더 해서 어느 쪽이 이겼는지 본다. 이긴 쪽의 경로에 지금 칸을 붙인다.
[0, 2, 4, 6, 7, 9]
0, 2, 4, 6번 칸을 두 칸씩 건너뛰며 밟고, 7과 9로 마무리한다. stairs[1], stairs[5], stairs[8] 의 100을 전부 피했다.
min을 두 번 계산하는 것
min(dyna(a), dyna(b)) 로 값을 구하고, 바로 아래에서 dyna(a) < dyna(b) 로 또 부른다. 같은 걸 네 번 부르는 셈이다.
메모이제이션 덕에 실제 계산은 한 번뿐이라 느려지지는 않는다. dict에서 꺼내는 것만 반복된다.
값과 경로를 한 번에 정하려면 min 대신 비교문을 쓰고 이긴 쪽에서 둘 다 갱신하는 형태가 된다. 그러면 min 이 주는 짧음이 사라진다. 어느 쪽이 나은지는 취향 같은데, 여기서는 min 을 살리고 비교를 한 번 더 하는 쪽을 골랐다.
마지막 하나를 떼는 이유
print(path[length][:-1])
path[length] 에는 끝에 붙여둔 비용 0짜리 가상 계단이 들어 있다. 실제로 밟은 칸이 아니므로 잘라낸다.
음수 인덱스가 그냥 통과하는 것
dp 는 dict라 dp[-1] 을 미리 넣어둘 수 있었는데 path 는 리스트다.
path = [[]] * (length + 1)
path[-1] 과 path[-2] 는 파이썬에서 뒤에서 세는 것이라 리스트의 마지막과 그 앞을 가리킨다. 에러가 나지는 않는다.
전부 빈 리스트로 초기화해뒀고, 그 자리들이 갱신되기 전에 읽히기 때문에 결과적으로 빈 리스트가 나와 맞게 돈다. dp 처럼 의도적으로 넣어둔 초기값이 아니라 우연히 맞는 쪽이다. path 도 dict로 두고 {-2:[], -1:[]} 로 시작했으면 dp 와 같은 방식이 됐을 것이다.