프로그래머스 [level2] 숫자 변환하기- python3

숫자 변환하기

문제 설명

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

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

제한사항

1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명

입출력 예 #1

x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2

x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

##입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

문제 풀이

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

    dp = [10000000]*(y+1)
    dp[x] = 0

    for i in range(x,y+1):
        if dp[i] == 10000000:
            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] == 10000000:
        return -1

    return dp[y]

문제 해석

기본적인 dp 문제입니다. dp 리스트를 생성한 후, 조건3개에 맞춰 값을 진행했을 때, 연산횟수가 해당 인덱스 값보다 적다면 값을 스위칭합니다.