[swift] 프로그래머스 - 점프와 순간 이동

프로그래머스

---

 

나의 풀이

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

 

좋은 아이디어가 생각나지 않아서 계속 헤매다

끝내 검색해서 풀었다.

 

문제는 최소한의 배터리만 사용하여 원하는 목적지까지 가길 바란다.

거리 1만큼 배터리 1이 소모되는데

순간이동을 하면 배터리가 소모되지 않는다

순간이동의 조건은 지나온 거리의 *2를 갈 때이다.

지나온 거리가 3이라면 6까지 순간이동

12라면 24까지 순간이동 할 수 있다.

 

지나온 거리의 *2라면

2의 배수는 무조건 순간이동을 할 수 있지 않나?

즉, 2의 배수를 순간이동하면 최소한의 배터리만 소모할 수 있지 않을까..?

 

이게 무슨 말이냐면

 

6의 거리만큼 가야 할 때

0 ~ 1 배터리 소모

1 ~ 2 순간이동

2 ~ 3 배터리 소모

3 ~ 6 순간이동

라는 식이 세워진다.

 

 

위 식을 도출하기 위해선

가야 하는 거리에서부터 / 2씩 나눠

짝수라면 순간이동

홀수라면 점프(배터리소모)를 하게 된다.

 

임의의 숫자로 43만큼의 거리를 최소한의 점프로 가야 한다면

43부터 나누기 2를 반복하여

 

43 (홀수, 배터리소모)

21 (홀수, 배터리소모)

10 (짝수)

5 (홀수, 배터리소모)

2 (짝수)

1 (홀수, 배터리소모)

0

 

총 4번의 점프만으로 43까지 갈 수 있다.

 

---