첫번째 풀이

# 실패

b = int(input())
cnt_arr = []

a=b
cnt = 0
while a>1:
    if a!=1:
        cnt+=1
    if a%3==0:
        a=a//3
    elif a%2==0:
        a=a//2
    else:
        a-=1
    # print('1:',a)
cnt_arr.append(cnt)

a=b
a-=1
cnt=1
while a>1:
    if a!=1:
        cnt+=1
    if a%3==0:
        a=a//3
    elif a%2==0:
        a=a//2
    else:
        a-=1
    # print('2:',a,cnt)
cnt_arr.append(cnt)

print(min(cnt_arr))

이건 솔직히 생각나는대로 막 풀어본 것이라 설명할 것도 없을 것 같다 ㅋㅋㅋ

두번째 풀이

# dp공부

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n+1)

for i in range(2,n+1):
    dp[i] = dp[i-1] + 1

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

print(dp[-1])

dp로 푸는 문제였다. 상상도 못했는데
대체 이런 알고리즘은 어떤 문제 어떤 상황에서 풀어야하는지 정말 아직까지도 잘 모르겠다ㅠㅠ
이거 이해하려고 아이패드에 그림을 그려가며 이해했다.

그림을 그리니 이해가 가긴 하는데 다음에 또 비슷한 문제가 나왔을때 풀 수 있을지...ㅠ
이런 알고리즘 문제는 비슷한 문제를 수학문제마냥 까먹지 않게 계속 풀어봐야하는 것 같다.