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

-Code

public class Solution {
    public int solution(int n) {
        int ans = 0;
        // 2배 이동이 공짜이므로 최대한 많이
        while(n != 0) {
            // 2배 이동이 안되면 1이동 후 에너지 사용
            if (n % 2 == 1) {
                ans++;
                n--;
                continue;
            }
            n /= 2;
        }

        return ans;
    }
}

처음에는 재귀를 통해서 해결하려나 시간 초과도 나고 로직 자체가 복잡해져서 못풀었습니다. 그래서 좀 찾아보니 2배로 이동하는게 에너지가 사용이 안되니 2의 배수가 아닌경우 1을 빼주면 이전 단계에서 1을 이동해서 배수를 맞춘것 이므로 최소한으로 에너지를 쓰면서 이동 할 수 있는 것을 알게 되어 해결했습니다.