점프와 순간 이동

import java.util.*;
 
public class Solution {
    public int solution(int n) {
        int ans = 0;
        while (n != 0) {
            if (n % 2 != 0) {
                n--;
                ans++;
            }
            n /= 2;
        }
        return ans;
    }
}

n까지 가는 경로에 규칙이 있다.

n = 5 -> 1 - 2 - 4 - 5

n = 6 -> 1 - 2 - 3 - 6

n = 5000 -> 1 - 2 - 4 - 8 - 9 - 18 - 19 - 38 - 39 - 78 - 156 - 312 - 624 - 625 - 1250 - 2500 - 5000

역순으로 생각하여 2로 나누다가, 나뉘어 떨어지지 않을 때 -1을 해주면 된다.

이는 n을 이진수로 변환했을 때의 1의 갯수와 같다.