백준12852 - 1로 만들기2

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

top down 방식을 이용하여 풀었다. 그런데 풀고 나서 보니 bottom up 방식이 더 편하게 느껴졌다. 한가지 주의할 점은 top down 방식으로 풀면 콜 스택이 깊어질 경우 프로그램이 재귀 호출이 깊어진다고 에러를 낸다는 것이다. 이 점만 주의하면 쉽게 풀 수 있다.

import sys
from copy import deepcopy

arr = [987654321 for i in range(1000001)]
trace = []
ans = [987654321, []]
N = int(input())

def topDown(x, num):
  if num > ans[0]:
    return
  if x == 1:
    if(ans[0] > num):
      ans[0] = num
      ans[1] = deepcopy(trace)
    return
  if x % 3 == 0 and arr[x // 3] > arr[x] + 1:
    arr[x // 3] = arr[x] + 1
    trace.append(x // 3)
    topDown(x // 3, num + 1)
    trace.pop()
  if x % 2 == 0 and arr[x // 2] > arr[x] + 1:
    arr[x // 2] = arr[x] + 1
    trace.append(x // 2)
    topDown(x // 2, num + 1)
    trace.pop()
  if arr[x - 1] > arr[x] + 1:
    arr[x - 1] = arr[x]+ 1
    trace.append(x - 1)
    topDown(x - 1, num + 1)
    trace.pop()

arr[N] = 0
trace.append(N)
topDown(N, 0)
print(ans[0])
for x in ans[1]:
  sys.stdout.write(str(x) + ' ')