#125 백준 파이썬 [1463] 1로 만들기 - 점화식

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

 

#Solution

점화식을 이용해푼다.

f(x)는 다음과 같은 값에서 최솟값을 가진다.

1) f(x-1) + 1

2) f(x/2) + 1

3) f(x/3) + 1

이 세 함수의 최소 값을 구해주면 된다.

 

재귀함수를 매번 호출하면 시간복잡도가 굉장히 커지므로 다이나믹 프로그래밍 즉, 리스트를 만들어 값을 매번 저장해주는 것이 속도 향상에 도움이 된다.

N = int(input())

result = [0 for _ in range(N + 1)]

for i in range(1, N + 1):
    if i == 1:
        result[i] = 0
        continue
    result[i] = result[i-1] + 1
    if i % 3 == 0 and result[i//3] + 1 < result[i]:
        result[i] = result[i//3] + 1
    if i % 2 == 0 and result[i//2] + 1< result[i]:
        result[i] = result[i//2] + 1
        
print(result[N])