[Swift] 프로그래머스 점프와 순간이동(lv. 2)

[Swift] 프로그래머스 점프와 순간이동(lv. 2)

 

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

2. 접근

건전지로 움직이는 거리를 최소화하려면...? 순간이동을 최대한 많이 하면 된다.

나는 처음부터 쌓아가는 것이 아니라, 거꾸로 distance를 절반 씩 나눠가면서 최소 건전지 사용량을 구하려고 했다.

'그리디 문제' 같은 것이므로, distance가 2로 나누어 떨어지면 2로 나누어버리고 answer(건전지 사용량)을 누적 합하지 않고 통과하고, 2로 나누어 떨어지지 않으면, distance가 2로 나누어 떨어질 때까지 계속 distance에서 1을 빼주고, 2로 나누어 떨어지면 다시 2로 나누어주는 반복문을 만들었다.

 

이 문제는 순간이동은 이제까지 온 거리에서 2배를 더 간다는 부분에서 아이디어를 얻으면 바로 풀 수 있는 문제였다.

 

 

3. 코드

import Foundation

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