import sys
input = sys.stdin.readline
from collections import deque
INF = 10**9
N = int(input())
DP = [INF]*(N+1)
last = {}
dq = deque()
dq.append(1)
DP[1] = 0
while dq:
n = dq.popleft()
if n*3<N+1:
if DP[n*3] > DP[n]+1:
DP[n*3] = DP[n]+1
last[n*3] = n
dq.append(n*3)
if n*2<N+1:
if DP[n*2] > DP[n]+1:
DP[n*2] = DP[n]+1
last[n*2] = n
dq.append(n*2)
if n+1<N+1:
if DP[n+1] > DP[n]+1:
DP[n+1] = DP[n]+1
last[n+1] = n
dq.append(n+1)
print(DP[N])
while 1:
print(N,end=" ")
try:
N = last[N]
except:
print()
break
가장 기초적인 DP문제인 1로만들기 문제에서 경로만 추가되었다.
last dictionary를 만들어서 DP값이 바뀔때마다 그전 값을 딕셔너리에 저장하고, 마지막에 last 값을 순서대로 출력하는 방식으로 구현하였다.
오늘의 교훈) 음... 열심히하자