[프로그래머스 2단계] 점프와 순간 이동

🔒 2단계 - 점프와 순간 이동

📌 테스트케이스 추가 힌트

해당 문제는 추가 테스트케이스가 필요하지 않았다.

✍️ 풀이법

해당 문제는 처음 1칸은 무조건 점프해야하고,
무한대로 순간이동을 할 수 있지만, 도착 지점을 넘어버리면 안 되기 때문에
순간이동 사이사이 점프를 배치해 주어 최솟값을 맞추어야 했다.

해당 문제를 해결하기에 앞서, 테스트케이스 5000이 어떻게 5가 되는지 생각해 보았다.
단순히 1칸 앞으로 가서 2를 곱해 나가면 
2 > ... > 1024 > 2048 > 4096 으로 남은 900칸을 점프해야 했다.

다음으로는 5000이니까, 단순히 5까지 점프, 또 순간이동 해 보았다. 
5 > ... > 2560 > 5120 으로 초과 해버렸다.

다른 방법이 필요했다.
어떻게 5000이 5번 만에 갔을까?

고민 끝에 문제를 반대로 생각해 보았고 5000에서 순간이동으로 0으로 가보기로 하였다.
5000 > 2500 > 1250 > 625 홀수를 만나 순간이동을 할 수 없었지만, 
이 말은 625를 만들면 5000으로 순간이동을 할 수 있다는 말이기도 했다.

여기서 한번 점프해보니, 624 > 312 > 156 > 78 > 39  홀수를 만나 멈추었고, 또 점프를 했다.
38 > 19 점프 18 > 9 점프 8 > 4 > 2 > 1 점프 0

정말 5번의 점프 만에 5000이 만들어진 것이다.


푸는 방법을 파악했으니 바로 식을 작성했다.

🗝️ 풀이

import java.util.*;

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