프로그래머스 코딩테스트 연습 Level2 - 점프와 순간 이동 [ Java ]

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

try 1

dp 문제라고 생각해서 bottom 방식의 dp로 풀었다

n번째 항 = 짝수일 경우 n/2번째 항 홀수일 경우 n/2번째 항 + 1 과 n-1 번째 항중에 작은 값

메모리 초과와 시간초과가 발생했다.

public class Solution {
    public int solution(int n) {
        int d[] = new int[n+1];
        d[0] = 0;
        for (int i = 1; i <= n; i++)
            d[i] = Math.min(d[i-1]+1, i % 2 == 0 ? d[i/2] : d[i/2] + 1);
        return d[n];
    }
}

 

try 2

n이 홀수일때와 짝수일 경우를 나누어 생각했다

public class Solution {
    public int solution(int n) {
        int count = 0;
        
        while (n != 0) {
            if (n % 2 == 0){
                n /= 2;
                continue;
            } else {
                n--;
                count++;
            }
        }
        return count;
    }
}

 

try 3

연산의 결과가 2진법의 1의 개수와 동일하다

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