코딩테스트 연습 - 점프와 순간 이동

Bottom-up 방식 (정확성✅ 효율성🚫)

문제 풀이 아이디어

문제의 조건에 의하면 순간이동은 비용이 들지 않으므로 최대한 순간이동을 활용해서 이동해야 합니다. n 위치에 도달하는 가장 효율적인 방법은 n / 2 위치에서 순간이동하는 것입니다. 만약 n이 홀수라면 (n - 1) / 2 위치에서 순간이동을 해서 n - 1로 온 다음에 이후에 배터리를 1칸 사용해서 n으로 오는 것입니다.

위 방법을 통해서 dp의 점화식을 구할 수 있습니다.

초기값: f(1) = 1
 
점화식
n이 짝수 일 때 = f(n / 2)
n이 홀수 일 때 = f((n - 1) / 2) + 1

코드

func solution(_ n:Int) -> Int {
    var cache = Array(repeating: 0, count: n + 1)

    func dp(_ i: Int) -> Int {
				// 초기값
        if i == 1 {
            return 1
        }
				// 점화식
        if cache[i] == 0 {
            if i % 2 == 0 {
                cache[i] = dp(i / 2)
            } else {
                cache[i] = dp((i - 1) / 2) + 1
            }
        }

        return cache[i]
    }

    return dp(n)
}

✋ 하지만

bottom-up 방식을 사용하면 정확성 테스트는 통과할 수 있지만 효율성 테스트는 통과할 수 없습니다. 시간복잡도가 O(N)인데 N은 최대 10억이기 때문입니다.

Top-down 방식 (정확성✅ 효율성✅)

문제 풀이 아이디어

시간복잡도는 O(N)이하로 줄여야 합니다. 원리는 bottom-up과 같습니다. n으로 가기 위해서는 n / 2에서 순간이동하는 것이 최선의 방법이라는 것입니다. 하지만 n을 1에서 시작하는 것이 아니라 n에서 시작해서 2로 나누어 가면서 배터리 사용량을 구합니다.

n이 짝수라면 그냥 n을 2로 나누면 됩니다. 순간이동은 비용이 들지 않기 때문입니다. n이 홀수라면 n에서 1을 빼서 짝수로 만들고 배터리 사용량을 1 추가합니다. 이렇게 해서 n이 0이 될 때까지 반복하면서 배터리 사용량을 구하면 됩니다.

이 경우 n을 2로 나누어가면서 원하는 비용을 구하기 때문에 시간복잡도는 O(logN)이 됩니다.

코드

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