[프로그래머스] Lv2. 숫자 변환하기 / DP 😑

숫자 변환하기

문제 설명

자연수 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

---

입출력 예xynresult

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):
    dp = [-1 for i in range(3 * y + 1)]
    dp[x] = 0
    for i in range(x, y):
        if dp[i] == -1:
            pass
        else:
            if dp[i + n] == -1:
                dp[i + n] = dp[i] + 1
            else:
                dp[i + n] = min(dp[i + n], dp[i] + 1)
            if dp[i * 2] == -1:
                dp[i * 2] = dp[i] + 1
            else:
                dp[i * 2] = min(dp[i * 2], dp[i] + 1)
            if dp[i * 3] == -1:
                dp[i * 3] = dp[i] + 1
            else:
                dp[i * 3] = min(dp[i * 3], dp[i] + 1)
    return dp[y]

DP를 이용해서 풀었다. 

 

다른 사람 풀이

def solution(x, y, n):
    answer = 0
    s = set()
    s.add(x)
    
    while s:
        if y in s:
            return answer
        temp = set()
        for num in s:
            if num + n <= y:
                temp.add(num + n)
            if num * 2 <= y:
                temp.add(num * 2)
            if num * 3 <= y:
                temp.add(num * 3)
        s = temp
        answer += 1
    return -1

set를 이용하여 BFS 형식으로 푼 방식이다.