n = int(input())
dp = [0] * (n+1)
if n == 1:
print(0)
elif n == 2:
print(1)
else:
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])
1부터 n까지 차례대로 구할 수 있는 최소한의 횟수를 구해나가는 방식이다.
우선 숫자 n은 n-1로 부터 +1 하는 계산으로 구할 수 있다. 그 다음 3으로 나누어 떨어지는 숫자의 경우와 2로 나누어 떨어지는 숫자의 경우 각각 dp[n//3], dp[n//2]으로 부터 그 값 들의 횟 수들을 비교하는 방법으로 구할수 있다.