문제

문제에 앞서 이문제를 top-down방식으로 해결하려 했지만 아무리 고민해도 해결이 안되었다.
이부분은 언젠가 해결해야 한다.

풀이

바텀업 방식으로 해결가능한데 먼저 점화식을 보여주자면

dp[i] = min(dp[i / 3], dp[i / 2], dp[i+1])이고

이에따라 바텀업으로 채워가면 된다.

코드

#입력
#첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

#점화식
#dp[i] = min(dp[i / 3], dp[i / 2], dp[i+1])

import sys

N = int(input())

dp = [0] * (1000000+1)
dp[2] = 1
dp[3] = 1

for i in range(4, N+1):
  dp[i] = dp[i-1] + 1

  if(i % 3 == 0):
    dp[i] = min(dp[i // 3] + 1, dp[i])

  if(i % 2 == 0):
    dp[i] = min(dp[i // 2] + 1, dp[i])

print(dp[N])

top-down으로 풀려했던 흔적들이 보인다 너무 힘들었다. 하지만 언젠가 이벽을 다시 만날거고
언젠가는 다시 넘어야 한다.