백준 1463 1로 만들기(재귀)

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

재귀를 썻는데 -1을 해주는 연산때문에 재귀가 100000개이상으로 늘어난다. 파이썬에서 재귀는 1000개까지 가능하다고하여 다시 썻다. 

dy=[0] * 1000001
import sys
n=int(sys.stdin.readline().rstrip())

def filter(n, b=0):
    if dy[n] != 0:
        return dy[n]

    if n ==1:
        return 0

    else:
        a=[]
        if n%3==0:
            a.append(filter(n // 3, 0) + 1)
        if n%2==0:
            a.append(filter(n // 2, 0) + 1)
        if b<6:
            a.append(filter(n-1, b+1) + 1)
            dy[n] = min(a)
            return dy[n]
        return n


print(filter(n))

b는 n일때 -1연산을 n-b까지만 해주는 장치이다.

다이나믹 프로그래밍으로 1부터 1000000까지 연산을 하는 풀이방법도 있던데 상상도 못했다. 아직 다이나믹프로그래밍은 많이 부족한 것 같다. 

부족한 점

1. b를 찍었다. b를 처음엔 2로 줬는데 오류가 나서 b를 1씩 늘려준 결과 6에서 답이나왔다.