12852번 1로 만들기 2

https://www.acmicpc.net/problem/12852

---

아이디어

우선 리스트를 2개 만드는데 하나(dp)는 1이 되는 연산의 최솟값을 저장하는 리스트 dp[n]=x은 n이 1이 되기 위해 연산이 최소 x번 필요하다.
다른 리스트(pre)는 경로를 추적하는 리스트이다. 어디서 왔는지.
pre[n] = x는 n에서 x로 가는 게 최적 경로라는 것이다.
예를 들면 n = 5일 때 pre[5] = 3, pre[3] = 1 이라서 5에서 3으로 가는 것, 3에서 1로 가는 것이 최적이라 경로는 5 3 1이 나올 것이다.

초기값

dp[2], dp[3] = 1, 1
pre[2], pre[3] = 1, 1

기본적으로 1을 빼주는 연산을 하지만, 3으로 나누어 떨어지거나 2로 나누어 떨어지면 저장된 값과 현재 값을 비교하여 더 작은 값으로 갱신해주어야 한다.

---

코드

n = int(input())
dp = [0]*(10**6+1) # 횟수
pre = [0]*(10**6+1) # 경로 추적

dp[2], dp[3] = 1, 1
pre[2], pre[3] = 1, 1
if n == 1:
    print(0)
    print(1)
    exit()

for i in range(4, n+1):
    dp[i] = dp[i-1]+1
    pre[i] = i-1
    if i % 3 == 0:
        if dp[i] >= dp[i//3]+1:
            dp[i] = dp[i//3]+1
            pre[i] = i//3
    if i % 2 == 0:
        if dp[i] >= dp[i // 2] + 1:
            dp[i] = dp[i // 2] + 1
            pre[i] = i // 2
print(dp[n])

answer = [n]
temp = pre[n]
while temp != 1:
    answer.append(temp)
    temp = pre[temp]
answer.append(1)

print(*answer)