BaekJoon 12852번 : 1로 만들기 (python)

BaekJoon 12852번 : 1로 만들기 2 (S1 46.95%)

동적 계획법과 최단거리 역추적 단계이다. 지금까지 했던 동적 계획법에서 최단거리 역추적을 어떤 방법으로 할지 정하면 되는 문제들로 구성되어 있다. 기본적으로 역추적 할 때의 상황은 값이 업데이트 될 때 마다 이루어진다. 그 후로는 기준이 되는 값에서 부터 해당 index를 타고타고 가서 답을 도출하게 된다.

• 기본적인 dp문제인 1로 만들기에서 역추적 조건을 더한 문제이다. 이 문제는 1부터 시작해서 n까지 최솟값으로 만드는 방식으로 작동한다.
• 만약 i3, i2, i+1의 값이 d[i]에 의해 업데이트 될 때 position의 인덱스들도 현재의 값으로 업데이트 된다. 즉, position[i3,i2,i+1] = i로 업데이트 될 수 있는 것이다.
• 그렇게 position배열에는 해당 숫자로 넘어오기 전의 index가 저장이 되어있게 된다. 그렇게 역추적을 진행하며 하나씩 찾아준다.

import sys
input = sys.stdin.readline

n = int(input())
d = [float('inf')] * (n+1)
position = [0] *(n+1)
d[1] = 0

for i in range(1, n) :
    if i*3 <= n :
        if d[i*3] > d[i] + 1 :
            d[i*3] = d[i] + 1
            position[i*3] = i
    if i*2 <= n :
        if d[i*2] > d[i] + 1 :
            d[i*2] = d[i] + 1
            position[i*2] = i
    if d[i+1] > d[i] + 1 :
        d[i+1] = d[i] + 1
        position[i+1] = i
        
path = [n]
print(d[n])
while n != 1:
    n = position[n]
    path.append(n)
print(*path)