[Programmers] Level 2 : 점프와 순간 이동

프로그래머스

간단하게 생각해보면, 매우 쉬운 문제이다.
N까지 도달하고 싶은데, 2배씩 건너뛸 수 있다고 한다. 그리고 1칸씩 이동할 수 있는데, 1칸씩 이동하는 횟수를 최소로 만들고자 한다.

뒤에서부터 생각해보자. N = 1000일때, 가장 이득인 방법은 N = 500에서 2배로 뛰는 방법일 것이다. 그리고 N = 250 에서 500으로 뛰고 ...

이러다 보면 N = 125에서 막히는데, 홀수이기 때문이다. 그래서 1칸 이동했다 치고, N = 124부터 보자. 이런식으로 N = 0이 될때까지 확인하면 된다. 간단하게 말하면 2로 나누면서 짝수일 경우 무조건 2배씩 이동하고, 홀수면 1칸 뒤로 이동하면 된다.

import java.util.*;

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