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

 

문제

프로그래머스

 

알고리즘

없음

 

풀이

반드시 필요한 순간에만 1칸 점프를 해야 건전지 사용량을 최소로 할 수 있다.

만약 순간이동을 하면 * 2 가 되고, 이는 반드시 짝수가 되므로 n이 홀수라면 마지막에 1칸 점프를 해야한다.

따라서 반대로 n에서부터 0까지 현재 위치가 짝수라면 순간이동을, 홀수라면 한 칸 점프를 하면 최소 건전지 사용량을 구 할 수 있다.

 

 

코드

import java.util.*;

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

        while(n > 0) {
            if(n % 2 == 0)
                n /= 2;
            else {
                n--;
                ans++;
            }
        }
        return ans;
    }
}