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

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

프로그래머스

조건

제한시간 : 30분 이내

생각보다 로직을 생각해 내기가 쉬웠던 문제였다.
이동할 방법은 두 가지
1. K칸을 점프 (점프. 건전지 사용량이 K칸만큼 줄음)
2. 현재 온 거리 * 2 (순간이동. 건전지 사용량이 줄지 않음)

즉, 순간이동이 가장 효율적이다.

5000 -> 2500 -> 1250 -> 625 -> [625-1] -> 312 -> 156 -> 78 -> 39 [39-1] -> 19 -> [19-1] -> 9 -> [9-1] -> 4 -> 2 -> 1 -> [1-1] -> 0

그냥, 홀수면 n값을 -1 해주면서 점프++ 를 해주면서 계속 나눠주면 됨.

public class Solution {
    public int solution(int n) {
        int ans = 0;
        while(n != 0) { // 0이면 종료
            if(n % 2 == 1) {
                ans++;
                n--;
            }
            n/=2;
        }
        return ans;
    }
}