[백준] #1463번 Dynamic Programming python

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

1463번: 1로 만들기

 

오늘도 DP 문제를 가져와 보았다.

 

 

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

연산을 사용하는 횟수의 최솟값을 출력하는 것이다.

 

입력으로 주어는 값을 x에 넣는다.

 

재귀를 이용하여 구현해준다.

 

해당 코드는 하향식으로 제일 큰 값에서 작은 값으로 바뀌도록 구성되었다.

 

 

x=int(input())

dp={1:0}

def rec(n):
    if n in dp.keys():
        return dp[n]
    if n%3==0 and n%2==0:
        dp[n]=min(rec(n//3)+1, rec(n//2)+1)
    elif n%3==0:
        dp[n]=min(rec(n//3)+1, rec(n-1)+1)
    elif n%2==0:
        dp[n]=min(rec(n//2)+1, rec(n-1)+1)
    else:
        dp[n]=rec(n-1)+1
    return dp[n]
print(rec(x))