[Programmers] 숫자 변환하기

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

원본

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=python3

프로그래머스

---

풀이

def solution(x, y, n):
    if x == y:
        return 0

    dp = [99999999 for _ in range(y+1)]
    dp[x] = 0
    
    for i in range(x, y+1):
        dp[i] = min(dp[i-n]+1, dp[i])
        # i가 2, 3으로 나눠지지 않으면 만들 수 없는 수다.
        dp[i] = min(dp[i//2]+1 if i%2==0 else 99999999, dp[i])
        dp[i] = min(dp[i//3]+1 if i%3==0 else 99999999, dp[i])
    
    return dp[y] if dp[y] != 99999999 else -1