프로그래머스 - 점프와 순간 이동 feat. 최소 연산횟수

 

당연히 DP 로 접근해야 한다고 생각하였습니다. 

하지만 배열을 만들어서 접근하게 될 경우 시간초과가 발생하여 다른 방법을 모색해야 했습니다.

import Foundation

func solution(_ n:Int) -> Int
{
    var answer: [Int] = [1,1,1]
    if n < 3 { return answer[n] }
    for i in 3...n {
        if i % 2 == 0 {
            let stemp = min(answer[i-1]+1, answer[i/2])
            answer.append(stemp)
        } else {
            let stemp = min(answer[i/2]+1, answer[i-1]+1)
            answer.append(stemp)
        }
    }

    return answer[n]
}

 

문제 이해하기

문제에서 현재 위치를 2배로 건너뛰는 것은 비용이 발생하지 않습니다, 그렇기 때문에 2로 나누어 떨어진다면 비용을 증가시키지 않고 만약 현재 위치가 2로 떨어지지 않는다면 -1 만큼 감소시키고 비용을 1씩 증가시키는 것으로 문제를 접근할 수 있겠습니다.

import Foundation

func solution(_ n:Int) -> Int
{
    var answer = 0
    var a = n
    
    while a > 0 {
        if a % 2 == 0 {
            a /= 2
        } else {
            a = a - 1
            answer += 1
        }
    }

    return answer
}

 

더 개선된 코드

import Foundation

func solution(_ n:Int) -> Int
{
    if n == 1 { return 1 }
    if n % 2 == 0 { return solution(n/2) }
    return solution(n/2) + 1
}