백준 - 1로 만들기 1463 파이썬

문제 

 

해결코드 

x = int(input())

# 초기화(dp가 1일 때, 연산횟수 0회)
dp = {1: 0}

# 재귀 (탑다운 방식)
def cal(n):
    if n in dp.keys():
        return dp[n]
    if (n % 3 == 0) and (n % 2 == 0):
        dp[n] = min(cal(n // 3) + 1, cal(n // 2) + 1)
    elif n % 3 == 0:
        dp[n] = min(cal(n // 3) + 1, cal(n - 1) + 1)
    elif n % 2 == 0:
        dp[n] = min(cal(n // 2) + 1, cal(n - 1) + 1)
    else:
        dp[n] = cal(n - 1) + 1

    return dp[n]

print(cal(x))

3과 2의 공통 배수를 처리하는 과정을 생각해내는 점이 포인트였고 참신했다