https://www.acmicpc.net/problem/1463 : 1로 만들기 <DP, top-down, bottom-up>

approach.txt

문제의 조건인 n이 1이 될 수 있는, 최솟값을 구할 수 있는 방법은
1. n/3
2. n/2
3. n-1
이 있다.
n에서 n/2, n/3, n-1을 거치면 횟수가 +1
한번 거친 후 조건을 n 번을 반복하므로
1 + f(n/2) ,1 + f(n/3),1 + f(n-1)
모든 조건을 거치면서 최솟값을 구한다.
예 n = 10일 때 n-1을 9번 거쳐간 값과 8번 거쳐간 후 n/2를 한 번 거쳐간 값과 비교 후 값이 작은 것을 사용한다.(이 경우 서로 같으므로 후자 값을 사용하지 않음)
앞의 값과 n-1을 7번 거쳐간 후 n/3을 한 번 거쳐간 값을 비교했을 때 후자의 값이 작으므로 이 값을 사용한다. (최솟값을 찾을 때까지 반복)

Greedy 알고리즘 같아 보이나 거쳐간 값을 비교하려면 전 값이 존재해야 하므로 DP가 어울림.

baekjoon1463.py

#####top-down#####
#@warning It is recursive version so can't be passed because input value is (i <= 1000000) but maximum recursion depth is over 994  
#@big-oh O(n)
d = [0] * 1000001
def f(n):
    if n == 1:
        return 0
    if d[n] > 0:
        return d[n]
    d[n] = f(n-1) + 1
    if n % 2 == 0:
        temp = f(int(n/2)) + 1
        if d[n] > temp:
            d[n] = temp
    if n % 3 == 0:
        temp = f(int(n/3)) + 1
        if d[n] > temp:
            d[n] = temp
    return d[n]
print(f(int(input())))

#####bottom-up#####
#@big-oh O(n)
def f(n):
    d = [0] * (n+1)
    d[1] = 0
    for i in range(2, n+1):
        d[i] = d[i-1] + 1
        if i % 2 == 0:
            temp = d[int(i/2)] + 1
            if d[i] > temp:
                d[i] = temp
        if i % 3 == 0:
            temp = d[int(i/3)] + 1
            if d[i] > temp:
                d[i] = temp
    return d[n]
print(f(int(input())))