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

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

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

문제풀이

숫자 N: 1 이상 10억 이하의 자연수 이기때문에 완전탐색이 불가능하기 때문에 다른 방법을 접근해야 된다.

점프를 최소로 하고 순간이동을 최대로 활용해야 하기때문에 역으로 n을 2로 나누면서 2로 나누어 떨어지지 않을때 마다 -1씩 해주고 점프 카운트를 증가시켜주면 된다. 

n == 1이 되는 순간까지 반복한다 ( 순간이동을 할려면 최소 한 번은 뛰어야 하기 때문에 )

 

코드

import java.util.*;

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

        return ans;
    }
}