[백준]1463

문제

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

풀이

Top-Down 방식과 Bottom-Up 방식 중 편한 방식을 사용하면 된다.

# Bottom-up
import sys

x = int(sys.stdin.readline().rstrip())
# 입력 조건만큼 배열 생성
d = [0] * 1000001

for i in range(2, x+1):
    d[i] = d[i-1] +  1
    if i % 2 == 0:
    # 최솟값은 min 함수 사용
        d[i] = min(d[i], d[i//2]+1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3]+1)
print(d[x])