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

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

프로그래머스

---

 

문제

 

 

풀이

이동의 가능한 경우의 수는 2가지 입니다.

1. K칸 점프
2. (현재까지 온 거리) x 2 위치로 순간이동

 

이때 점프하는 칸 수를 최소화 하고 싶기 때문에 순간 이동을 하다가 필요한 경우에 1칸 점프를 해야 합니다.

 

0칸에서 N칸으로 이동을 N칸에서 0칸으로 이동이라고 생각하면,

1. (현재까지 온 거리) x 2 위치로 순간이동은 (현재 위치한 칸 / 2)의 위치로 순간이동 하는 것과 마찬가지 입니다. 따라서 현재 위치한 칸이 N이라고 하면 N /= 2 연산을 하면 됩니다.
2. K칸 점프하는 것은 1칸씩 점프를 하기 때문에 N -- 를 하면 됩니다.

 

따라서 N이 2로 나눠지면 1번 연산을 하고, 2로 나눠떨어지지 않으면 2번 연산을 하면 됩니다.

 

 

소스코드

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

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

        return ans;
    }
}