1463

 

import sys
input = sys.stdin.readline

n = int(input())
cnt = 0

while n > 1:
    if n % 3 == 0:
        n = n/3
    elif n % 3 == 1:
        n -= 1
    else:
        n = n/2

    cnt += 1

print(cnt)

그냥 논리 세워서 풀려고 했는데

틀렸다고 함

dp 구현해야 하나 본데 너무 오랜만이라 생각이 나지 않아서 책 뒤적거려봄

 

import sys
input = sys.stdin.readline

n = int(input())

dp = [0 for _ in range(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])

이렇게 해결했다

 

#동적계획법