PGS / 숫자 변환하기 / Python

PGS / 숫자 변환하기

풀면서

dp로 풀려고 시도했다. 뭔가 딱 dp 문제인 것 같았다. 근데 계속 시간초과가 떴다 !

import sys
sys.setrecursionlimit(1000000)

def solution(x, y, n):
    answer = 0
    
    dp = [1000000] * (1000001)
    dp[x] = 0
    
    def dp1(dp, x, y, n):
        temp = [x*3, x*2, x+n]
        
        if min(temp) > y:
            return
        
        for t in temp:
            if t > y:
                continue
            
            dp[t] = min(dp[t], dp[x]+1)
            
            dp1(dp, t, y, n)
            

    dp1(dp, x, y, n)
            
    return dp[y] if dp[y] != 1000000 else -1

대체 어디서 시간 단축을 하나.
결국 풀이를 찾아봤다.

code ⌨️

def solution(x, y, n):
    answer = 0
    
    dp = [1e7] * (1000001)
    dp[x] = 0
                        
    for i in range(x, y+1):
        # 만들 수 없는 수
        if dp[i] == 1e7:
            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] != 1e7 else -1

풀고 나서👆👀

재귀 함수없이 for문으로 충분히 해결할 수 있는 문제였다.
추가로 10의 제곱 수 표현도 이제 잘 이용하자.