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

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

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

 

풀이

 

규칙만 잘 생각해 낸다면 매우 쉬운 문제입니다.

점프는 이동에 cost가 발생하지만 순간이동은 그렇지 않기 때문에 최대한 순간이동을 이용해야 합니다.

따라서 N을 2로 나눠가면서 나머지가 생기는 경우만 한칸을 점프 이동한다는 알고리즘으로 문제를 해결합니다.

 

import java.util.*;

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

        while(n>1){
            //1칸 점프 이동
            if(n%2 == 1)
                ans++;
            n = n/2;
        }
        //0에서 1로 갈 때는 무조건 점프!
        ans++;
        
        return ans;
    }
}