[백준] 1로 만들기

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

분류 ::: dp 

 

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

 1. DP(dynamic programming) -bottomup

#1로 만들기
#https://www.acmicpc.net/problem/1463
import sys
sys.stdin = open("input.txt","r")
n=int(input())
dp=[0]*(n+1)
for i in range(2,n+1):
    #1뺴는 경우
    dp[i]=dp[i-1]+1
    #2로 나누어 떨어지는 경우
    if i%2==0:
        dp[i]=min(dp[i],dp[i//2]+1)
    #3으로 나누어 떨어지는 경우
    if i%3==0:
        dp[i]=min(dp[i],dp[i//3]+1)

print(dp[n])

 

3. 오답원인

 1. top- down

: 메모리 초과가 난다 . 왜일까? 

#1로 만들기 -Top-down
#https://www.acmicpc.net/problem/1463
import sys
sys.stdin = open("input.txt","r")
sys.setrecursionlimit(10**6)
def DFS(i):
    if i==1:
        return 0
    if dp[i]>0:
        return dp[i]

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


if __name__=="__main__":
    n = int(input())
    dp = [0] * (n + 1)
    print(DFS(n))

 

4. 알게된 점