[프로그래머스][Java] Lv.2 점프와 순간이동

문제 설명

 

한 번에 K칸을 앞으로 점프하거나, (현재까지 온 거리)*2 에 해당하는 위치로 순간이동 할 수 있는 슈트가 있다.

순간이동을 하면 건전지 사용량은 줄지 않지만, 점프를 하면 점프한 거리만큼 건전지를 사용하게 된다.

 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution을 만드시오.

---

풀이 과정

1. 처음 위치 0을 움직이는 것보다 도착지점 N을 이용해 계산하는 것이 더 빠르다.
2. 건전지를 최소한으로 사용하기 위해 순간이동을 최대한 많이 이용한다.
3. N에서 부터 시작하여 2로 나눠떨어질 때 계속 순간이동을 하고, 순간이동이 안되는 순간에만 -1을 해주며 0을 만든다.

 

전체 코드

import java.util.*;

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

	//0이 될때까지 반복함.
        while(n>0){
            //2로 나눌 수 있는 한 끝까지 나누기.
            if(n%2==0)
                n/=2;
            else{
                n--;
                ans++;
            }
        }
        return ans;
    }
}