1463번 파이썬

import sys
input = sys.stdin.readline
n = int(input())
p=[0 for _ in range(n+1)]
if n>=2:
  p[2]=1
if n>=3:
  p[3]=1
for num in range(4,n+1):
  cnt=0
  temp=[p[num-1]+1]
  if num%2==0:
    temp.append(p[int(num/2)]+1)
  if num%3==0:
    temp.append(p[int(num/3)]+1)
  p[num]=min(temp)
print(p[n])