[programmers/py] 숫자 변환하기

숫자 변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제 설명

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

문제 풀이

• dp를 활용해 *2, *3, +n의 횟수를 저장

def solution(x, y, n):
    dp = [float('inf')] * (y+1)
    dp[x] = 0
    
    if x == y:
        return 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)
    
    if dp[y] == float('inf'):
        return -1
    return dp[y]