백준 - 12852 : 1로 만들기 2 (S1)

 1N = int(input())
 2
 3dp = [0, 0] + [10**6]*(N-1)
 4bt = [0]*(N+1)
 5
 6for i in range(2, N+1):
 7    dp[i] = min(dp[i-1]+1, dp[i])
 8    bt[i] = i-1
 9
10    if i%3 == 0:
11        if dp[i//3]+1 < dp[i]:
12            dp[i] = dp[i//3]+1
13            bt[i] = i//3
14    if i%2 == 0:
15        if dp[i//2]+1 < dp[i]:
16            dp[i] = dp[i//2]+1
17            bt[i] = i//2
18        dp[i] = min(dp[i], dp[i//2]+1)
19
20print(dp[N]다
21i = N
22while i != 1:
23    print (i, end=' ')
24    i = bt[i]
25print (1)