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

프로그래머스

 

 

이해하기

처음에는 가능한 경우의 수를 다 해봐야 하나 싶었다.

하지만 제한 사항을 보니 N은 10억 이하의 자연수... 

도저히 감이 안 잡혀서 참고하여 풀이하였다.

 

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

 

점프는 할 때마다 건전지가 사용되니 건전지를 최소로 사용하기 위해서는 점프보다 순간이동을 많이 해야만 한다.

또 내가 위에서 생각했던 방식은 bottom-up(0부터 N까지)이고 이와 반대되는 top-down(N부터 0까지)가 경우의 수가 훨씬 적다고 한다.

 

• N이 0이 될 때까지
  • N이 짝수면 N /= 2
  • N이 홀수면 N -= 1

 

문제풀이

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

        while (n != 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n -= 1;
                ans++;
            }
        }

        return ans;
    }
}

 

 

풀이만 보면 정말 간단한데 방법을 떠올리기가 넘 어려웠다.