[프로그래머스] [DP] 숫자 변환하기

숫자 변환하기

프로그래머스

 

• 풀이 (bottom-up)

def solution(x, y, n):
    dp = [float('inf')] * (y + 1)
    dp[x] = 0

    for i in range(x, y + 1):
        if dp[i] == float('inf'):
            continue
        if i + n <= y:
            dp[i + n] = min(dp[i + n], dp[i] + 1)
        if i * 2 <= y:
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)
        if i * 3 <= y:
            dp[i * 3] = min(dp[i * 3], dp[i] + 1)
    
    return dp[y] if dp[y] != float('inf') else -1

 

• 내 풀이(top-down)
  • 예제는 맞는데 돌리면 50/100 런타임에러
  • -> 재귀도는 과정에서 런타임 에러나는 듯함
  • -> 재귀 깊이 제한 sys.setrecursionlimit(1500000) 두니까 통과

import sys
sys.setrecursionlimit(1500000)

answer=float('inf')
def solution(x, y, n):
    answer = 0
    dp=[-1 for _ in range(y+1)]
    dp[x]=0

    def recur(cur):
        if cur<x:
            return 23425234234
        if dp[cur]!=-1:
            return dp[cur]
        if cur==x:
            return dp[cur]
        
        tmp=float('inf')
        if cur - n >= x:
            tmp=min(tmp,recur(cur-n)+1)
        if cur%2==0:
            tmp=min(tmp,recur(cur//2)+1)
        if cur%3==0:
            tmp=min(tmp,recur(cur//3)+1)
        dp[cur]=tmp
        return dp[cur]
    
    recur(y)
    if dp[y]>=1000001:
        answer=-1
    else:
        answer=dp[y]
    return answer