[프로그래머스] 점프와 순간 이동 -JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

순간이동 기능은 온 거리 x2 라고 한다.

위치가 6일때 생각해보면

0 -> 1 점프

1 ->2 순간이동

2 ->4 순간이동

4 ->6 점프로 총 3의 에너지를 사용했다.

 

하지만 

0 -> 1 점프

1 ->2 순간이동

2 ->3 점프

3 ->6 순간이동을 하면 2의 에너지 사용으로 최소 에너지가 된다.

 

결국 마지막은 점프를 통해 위치에 도달해야만 최소 에너지가 될 수 있다.

 

역으로 6에서 2로 나눴을 때 3

3은 2로 나눌 수 없으니 -1하고 2 에서 2로 나누면 1

1이 되면 최소값을 구한 것이다.

마지막에 +1만 해주면 될 것이다.

import java.util.*;

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