[Javascript] 점프와 순간 이동 (12980)

문제링크

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

 

접근 방법

규칙을 찾는 문제이다.

K칸을 가면 K만큼의 건전지가 필요하지만 순간이동에는 건전지가 필요하지 않다.
즉, 순간이동을 최대한 사용하는 문제이다.

순간이동만 사용할 시 1-> 2 -> 4 -> 8 -> 16 .. 이런식으로 2배씩 증가하는데

반대로 n에서 n / 2가 성립할때에는 건전지가 들지 않는다는 말이다.

즉 n = 5000 일때
5000 -> 2500 -> 1250 -> 625 -> 624 -> 312 -> 156 -> 78 -> 39 -> 38 ...

이처럼 n이 홀수 일때 건전지 + 1을 해주면 쉽게 정답을 구할 수 있다.

 

function solution(n) {
  var ans = 0;

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

  return ans;
}