Level2 - 점프와 순간 이동

한 칸 이동은 +1 

두 칸 이동은 +0

 

#1 5 -> 2번만에 

#2 6 -> 2번만에

#3 5000 -> 5번만에 

 

입출력 예 #2
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.

 

(1)

0 부터 어떻게 하면 5까지 아니면 6까지 5000까지 몇번만에 갈지를 생각하느라 고생을 오래 했다. 한칸 이동인 경우와 두 칸 이동인 경우를 DFS로 하여 탐색을 하면 답이 나오지만 범위가 1억까지 있으니 DFS는 무조건 안된다.

 

(2) 

해설을 보니 반대로 접근을 한다. 5000이 있으면 2로 계속 나누고 홀수이면 +1

해설을 보고 많이 어이없었다. 하지만 좋은 접근방법을 알게 됬다.

 

 

public class Solution {
    public int solution(int n) {
         int ans = 0;

        while(n!=0){
            if(n%2==1) ans++;
            n /=2;
        }

        return ans;
    }
}