[파이썬/백준 1463번] 1로 만들기

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

해도.. 해도.. 해도해도..

동적계획법 풀이를 보면 아..! 하는데

왜 나는 구현을 못 하는 것이지...

 

dp의 인자값을 N값으로 둘 생각 조차 못했다..

그냥 연산 한 다음에 중복 빼고 거기서 있나 찾아보기..로 생각했는데

아무리 생각해도 메모이제이션을 쓸 만한게 없다 했더니 휴..

 

언제쯤 구글링 없이 내 힘으로 문제를 풀 수 있을까..

 

N=int(input())
dp=[0]*(N+1)
for i in range(2,N+1):
    dp[i]=dp[i-1]+1
    if i%3==0:
        dp[i]=min(dp[i],dp[i//3]+1)
    if i%2==0:
        dp[i]=min(dp[i],dp[i//2]+1)
    
print(dp[N])