[백준] 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

탑다운, 바텀업 두가지 방식으로 풀긴 했는데, 탑다운 방식으로 하니까 시간초과가 났다.

max_num = 10**20

def solution(n,count):
    global max_num
    if n == 1:
        max_num = min(max_num,count)
    if n % 3 == 0:
        solution(n//3,count+1)
    if n % 2 == 0:
        solution(n // 2, count +1)
    if n > 1:
        solution(n-1,count+1)
    return max_num



def solution2(n):
    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)
    return dp[n]

input = int(input())
print(solution(input,0))
print(solution2(input))