[Python]1463. 1로 만들기

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

1463번: 1로 만들기

---

 

 

#Top-down 방식 : 재귀호출 이용
import sys
sys.setrecursionlimit(10000000) #재귀 한도를 늘려준다. RecursionError 방지
 
def dp(x):
    if x == 1:
        m[x] = 0
        return m[x]
 
    if m[x] > 0:
        return m[x]
 
    m[x] = dp(x-1)+1 # 빼기 1 연산, 메모이제이션 + 초기화 기능
 
    if x % 3 == 0: # 나누기 3 연산, 메모이제이션
        div3 = dp(x//3)+1
        m[x] = min(m[x], div3)
 
    if x % 2 == 0: # 나누기 2 연산. 메모이제이션
        div2 = dp(x//2)+1
        m[x] = min(m[x], div2)
 
    return m[x]
 
x = int(input())
m = [0]*(10**6+1)
answer = dp(x)
print(answer)

 

# Bottom-up 방식 : for 문 이용
x=int(input())
dp=[0]*(x+1)
dp[1] = 0
for i in range(2,x+1):
    dp[i] = dp[i-1]+1
    if i % 3 == 0:
        div3 = dp[i//3]+1
        dp[i] = min(div3, dp[i])
    if i % 2 == 0:
        div2 = dp[i//2]+1
        dp[i] = min(div2, dp[i])
print(dp[x])
 
'''
# input
572

# output
10

# solution
572 571 570 190 189 63 21 7 6 3 1
'''