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

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

풀이

1. 처음은 dp로 접근했다. 답은 나오는데 유효성 검사에서 절대절대절대 통과할 수가 없음.. 숫자의 범위가 1이상 10억이하.......................

2. 따로 규칙을 찾아보니까 2의 거듭제곱은 모두 1, 그 기점으로 숫자가 바뀐다.
   -> 2의 제곱에 뭐가 있구나...를 알았고, 알고보니! 비트로 변환했을 때 1의 개수가 답이었다!!!! 대박

3. 그렇다면 Integer.bitCount()로 1의 개수를 세어주자~ 2진수로 바꿔서 1의 개수를 세주는 엄청난 함수!

코드

import java.util.*;

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

dp 코드(효율성 테스트 실패)

public class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 1];

		dp[1] = dp[2] = 1;
		for (int i = 3; i <= n; i++) {
			dp[i] = Math.min(dp[i - 1] + 1, i % 2 == 0 ? dp[i / 2] : dp[i / 2] + 1);
		}

		return dp[n];
    }
}