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

문제 링크

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

프로그래머스

 

풀이

처음엔 DP 문제인가? 했는데 N의 최댓값이 10억이길래 DFS 문제인가? 했는데 결국은 그냥 단순 구현 문제였다.

순간 이동을 해서 N이 될 수 있는 경우에는 순간 이동을 하고, 순간 이동을 할 수 없을 때는 1칸씩만 점프한다.

정답 코드

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

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

        return ans;
    }
}

 

 

*

다른 사람 풀이를 봤는데 충격적이었던 것

import java.util.*;

public class Solution {
    public int solution(int n) {
        return Integer.bitCount(n);
    }
}

 

이렇게 간단하게 풀 수 있다니..