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

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

 

소요시간 : 7분

 

이 문제는 사실.. 며칠전에 잠시 고민했었던 것....

모르겠어서 그냥 패스하고 나중에 풀어야지 하다가 오늘 다시 풀었다

오늘은 좀 생각하니 바로 떠올랐다.

n이 엄청나게 커서 전부 다 해보는 건 말도 안되고 일단,

최대한 x2 이동 (순간이동)을 해야하니 n이 짝수일 땐 나누기2가 가능하니 그냥 나누고

홀수일땐 이동을 +1만하고 다시 나누기 2를 하면 총 건전지 사용횟수가 나올 것이라 생각들었다.

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

    return ans;
  }
}