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

숫자 변환하기

문제 설명

자연수 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합니다.

---

풀이 및 소스코드

실패한 코드

DFS로 구현해서 작동은 하나 시간복잡도 실패.

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    
    var result = 9999999
    
    func dfs(_ depth: Int,_ now: Int, _ target: Int){
        if now == target && result > depth{
            result = depth
            return
        }
        if now > target{
            return
        }
                
        dfs(depth+1, now * 2, y)
        dfs(depth+1, now * 3, y)
        dfs(depth+1, now + n, y)
        
        return
    }
    
    dfs(0, x, y)
    return result == 9999999 ? -1 : result
}

트리 자료구조를 이용해서 풀었으나 실패.

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    
    var tree = [Int](repeating: 0, count: 1000000)
    tree[0] = x
    var value = 0
    var idx = 1
    
    
    while true{
        let parent = (idx - 1) / 3
        
        if idx % 3 == 1{
            value = tree[parent] + n
        }
        if idx % 3 == 2{
            value = tree[parent] * 2
        }
        if idx % 3 == 0{
            value = tree[parent] * 3
        }
        
        tree[idx] = value
        
        if value == y{
            break
        }
        if idx == 10000{
            return -1
            
        }
        
        idx += 1
    }
    
    var parent = idx
    var level = 0
    while parent != 0{
        level += 1
        parent = (parent - 1) / 3
    }
    return level
}

DP를 이용해서 풀었지만 구글링을 통해..

import Foundation
var max = Int.max

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    
    func adove1(_ x: Int, _ num: Int) -> Bool{
        return (num >= x)
    }
    func DivideRange(_ num: Int, _ divider: Int) -> Bool{
        return (x...y) ~= num/divider && num % divider == 0
    }
    
    var dp = [Int](repeating: 0, count: y + 2)
    
    for i in x+1...y+1{
        var a = max, b = max, c = max
		
        //만약 i를 식을 반대로(i-n, i/3, i/2)를 통해 만들어 진다면
        //i는 만들어 질 수 있는 숫자
        //만들어 각 수의 만들어 질 수 있는 최소의 숫자를 기록해놓고
        //그 수를 살펴가며 쌓아나감, 처음으로 만들 수 없다면 max저장
        if DivideRange(i, 3) {
            a = dp[i/3]
        }
        
        if DivideRange(i, 2){
            b = dp[i/2]
        }
        
        if adove1(x, i-n){
            c = dp[i-n]
        }
                
        var d = min(a, b)
        d = min(d, c)
        
        dp[i] = (d < max) ? d+1 : max
    }
    
    return dp[y] < max ? dp[y] : -1
}