프로그래머스 점프와 순간 이동(java)

문제

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

프로그래머스

문제에서 이동하는 방법은 두가지가 있다.

1. 점프

2. 순간이동

 

여기서 점프하는 칸수만큼 건전지를 사용하게 된다.

반면 순간이동은 현재까지 움직인 칸수만큼 이동하는데 건전지는 사용하지 않는다.

즉 순간이동을 최대한 많이해서 점프를 적게 할 수 있게 해야한다.

 

여기서 중요한 것은 순간이동은 현재까지 움직인 칸수라는 것이다. 현재까지 이동한 칸수를 n이라고 하면 순간이동을 하면 2n칸이 된다. 즉 순간이동을 하면 짝수라는 뜻이다.

이러한 특징을 활용해서 생각을 하면 이동해야 하는 칸수인 n이 홀수, 짝수에 따라 경우의 수를 나누어 주면 된다.

n이 짝수이면 n / 2만큼 이동후에는 순간이동을 하기 때문에 건전지를 사용하지 않아도 된다.

반면 n이 홀수라면 n -1 만큼 이동후 1칸을 이동해야 한다.

 

예를 들어 n = 5라고 가정하면 n은 홀수다. n에서 1을 n은 4가 되고 1칸 점프한다.

n은 짝수일 때는 n을 2로 나눈 몫으로 값을 넣어준다.

n /= 2 = 2

n /= 2 = 1

 

n이 다시 홀수이므로 1칸 점프를 한다.

 

코드로 작성하면

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;
    }
}