프로그래머스 - 점프와 순간 이동 문제 (자바)

programmers.co.kr/learn/courses/30/lessons/12980

코딩테스트 연습 - 점프와 순간 이동

개념만 떠올리면 간단하게 해결할 수 있는 문제

 

특정지점에 도달하기 까지 이상적인 경우는 그 지점의 절반 위치에서 순간이동을 하는 것이다.

순간이동으로 도착하지 못하는 경우만 건전지를 사용하면 된다.

 

문제의 예시인 5를 보면

 

5의 절반은 2.5로 나누어 떨어지지 않기 때문에 4에서 건전지를 1만큼 사용해서 이동

4의 절반은 2로 나누어 떨어지기 때문에 2에서 순간이동

2의 절반은 1로 나누어 떨어지기 때문에 1에서 순간이동

1의 절반은 0.5.로 나누어 떨어지지 않기 때문에 0에서 건전지를 1만큼 사용해서 이동

 

식으로 하면

 

5 - 1 = 4 (건전지 1만큼 사용)

4 / 2 = 2

2 / 2 = 1

1 - 1 = 0 (건전지 1만큼 사용)

 

이렇게 건전지 2를 사용하여서 0에서 5까지 도달할 수 있다.

// 프로그래머스 점프와 순간이동 문제
public class Solution {
    public int solution(int n) {
        int ans = 0;
        while(n != 0) {
            if(n % 2 != 0) {
                n = n - 1;
                ans++;
            }
            n = n / 2;
        }
        return ans;
    }
}