정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
1로 만들기 문제에 N을 1로 만드는 방법에 포함되는 수를 출력해야 함.
N = int(input())
dp = [0]*(N+1) # 횟수의 최솟값
pre = [0]*(N+1) # 최소 경로
for i in range(2,N+1):
dp[i] = dp[i-1] + 1 # 1 빼기
pre[i] = i-1
if i%2==0 and dp[i]>dp[i//2]+1: # 2로 나누기
dp[i] = dp[i//2]+1
pre[i] = i//2
if i%3==0 and dp[i]>dp[i//3]+1: # 3로 나누기
dp[i] = dp[i//3]+1
pre[i] = i//3
print(dp[N])
now = N
while True:
print(now, end=' ')
if now==1: break
now = pre[now]