[프로그래머스] 숫자 변환하기 (파이썬)

난이도 : LV2

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

문제해결 아이디어

• x가 y가 될때 까지의 최소 연산을 요구하는 문제이다.
• dp를 사용하면 시간초과 없이 해결할 수 있다고 생각했다.

소스코드

def solution(x, y, n):
    INF = int(1e9)
    dp = [INF] * (y+1)    
    dp[x] = 0
    cnt = 0
    for i in range(x+1,y+1):
        if i % 2 == 0:
            dp[i] = min(dp[i//2]+1, dp[i])
        if i % 3 == 0:
            dp[i] = min(dp[i//3]+1, dp[i])
        
        dp[i] = min(dp[i-n]+1, dp[i])
    
    return -1 if dp[y] == INF else dp[y]