[Backjoon] 1463_1로 만들기 (python 파이썬 코드)

# 초기 접근 첫번째로 시도했던 코드 (탑다운방식)
import math,sys
sys.setrecursionlimit(200000)

x = int(input())
cnt = 0
array=[0 for i in range(int(math.pow(10,6))+1)]
def dynamic(x, cnt, array):
    if x%3 == 0:
        if array[int(x / 3)] > cnt+1 or array[int(x / 3)] ==0:
            array[int(x / 3)] = cnt+1
            dynamic(x/3, cnt+1, array)

    if x%2 == 0:
        if array[int(x / 2)] > cnt+1 or array[int(x / 2)] ==0:
            array[int(x / 2)] = cnt+1
            dynamic(x / 2, cnt + 1, array)
    if x - 1 > 1:
        if array[int(x - 1)] > cnt + 1 or array[int(x - 1)] ==0:
            array[int(x - 1)] = cnt + 1
            dynamic(x - 1, cnt + 1, array)

dynamic(x, cnt, array)
print(array[1])

# Top_down 방식 (초기접근)

Top_down방식은 가장 큰 문제를 시작으로 작은 문제를 호출하여 답을 찾는 방식이고,

Bottom-up은 가장 작은 문제들 부터 답을 구해가며 큰 문제의 답을 찾는 방식이다.

처음에는 Top_down방식을 통해 접근하여 적은 수의 입력에 대해서는 답이 나왔지만

큰 수를 입력하면 런타임 에러가 났다.

import math

x = int(input())
n=1
cnt = 0
arr=[0 for i in range(int(math.pow(10,6))+1)]

for i in range(2,x+1):
    arr[i] = arr[i-1] + 1
    if i % 2 == 0:
        arr[i] = min(arr[i], arr[int(i/2)] + 1)
    if i % 3 == 0:
        arr[i] = min(arr[i], arr[int(i/3)] + 1)
print(arr[x])

# Bottom-up 방식

그래서 위와 같은 Bottom-up 방식을 이용하여 시간과 메모리 사용량을 아껴서 해결하였다.