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

프로그래머스

---

성공 풀이

func solution(_ x: Int, _ y: Int, _ n: Int) -> Int {
    var dp = Array(repeating: Int.max, count: y+1)
    dp[x] = 0
    for i in x..<y where dp[i] != Int.max {
        let num1 = i + n
        let num2 = i * 2
        let num3 = i * 3
        
        if num1 <= y {
            dp[num1] = min(dp[i]+1,dp[num1])
        }
        if num2 <= y {
            dp[num2] = min(dp[i]+1,dp[num2])
        }
        if num3 <= y {
            dp[num3] = min(dp[i]+1,dp[num3])
        }
    }
    return dp[y] == Int.max ? -1 : dp[y]
}

풀이 키워드

DP
최소 연산 횟수를 구하기 위해 DP를 활용했다.
애매하게 BFS를 사용했을 때 시간초과가 나왔기 때문에
보편적인 상황에서 시간복잡도에 유리한 DP로 풀었다.

dp배열을 Int.max로 초기화 시킨 뒤
dp[x]에는 count의 시작을 위해 0을 넣는다.

dp는 해당 숫자의 최소 연산 횟수를 저장하는 역할을 하기 때문에
dp[y]배열을 호출하면 y의 최소 연삿 횟수가 나온다.