[백준] 1463번_1로만들기

문제 링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

n = int(input())
d = [0]*(n+1)
for i in range(2,n+1):
    d[i] = d[i-1] + 1
    if i%2 == 0 and d[i] > d[i//2]+1:
        d[i] = d[i//2]+1
    if i%3 == 0 and d[i] > d[i//3]+1:
        d[i] = d[i//3]+1
print(d[n])

bottom-up 방식으로 풀었다.

파이썬은 재귀를 사용하게 되는 top-down 방식으로 풀면 시간과 메모리 모두 많이 쓴다기에 dp 다시 차근차근 풀어보며 bottom-up으로 풀어나가보려 한다.