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

점프와 순간 이동

문제 링크

점프와 순간 이동

분석

n칸을 이동하려고 할 때, 사용해야 하는 건전지 사용량의 최솟값을 구해 반환해야합니다.

순간이동에는 건전지를 사용하지 않지만, 점프로 이동한 칸만큼 건전지를 사용하게 됩니다.

순간이동은 현재까지 온 거리 x 2에 해당하는 위치로 순간이동 할 수 있습니다.
점프의 경우 원하는 칸만큼 이동할 수 있습니다.

이번 문제는 크게 2진수로 변환하는 방법과 도착지를 기준으로 계산하는 방법이 있습니다.

n을 2진수로 변환했을 때 1의 개수가 필요한 점프의 횟수가 됩니다.
$n = 6$일 경우를 예로 들면 다음과 같습니다.

• 0 $\rightarrow$ 1 점프
• 1 $\rightarrow$ 2 순간이동
• 2 $\rightarrow$ 3 점프
• 3 $\rightarrow$ 6 순간이동
• 6의 2진수 110

도착지를 기준으로 계산할 경우 다음과 같습니다.

• n이 짝수일 경우 순간이동으로 이동이 가능하기 때문에 $n / 2$로 되돌아가는 계산을 수행합니다.
• n이 홀수일 경우 점프로만 이동이 가능하기 때문에 $n - 1$로 되돌아가는 계산을 수행합니다.
• 이 과정을 반복하면 점프 횟수를 알 수 있고, 이것으로 배터리 사용량을 알 수 있습니다.

풀이

int solution(int n)
{
    int ans = 0;
    
    // 2진수로 변환하기 위한 반복문
    while (n)
    {
        // 현재 비트가 1일 경우
        if (n % 2 == 1)
        {
            ++ans;
        }
        
        // 다음 비트를 연산하기 위한 준비
        n /= 2;
    }

    return ans;
}

성능 요약

시간 복잡도는 $O(log n)$입니다.

• 2진수로 변환하는 반복문 $O(log n)$

공간 복잡도는 추가적인 공간을 사용하지 않기 때문에 $O(1)$입니다.

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.16MB)
테스트 3 〉 통과 (0.01ms, 4.18MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 3.68MB)
테스트 7 〉 통과 (0.01ms, 4.17MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.19MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 4.14MB)
테스트 14 〉 통과 (0.01ms, 4.2MB)
테스트 15 〉 통과 (0.01ms, 3.67MB)
테스트 16 〉 통과 (0.01ms, 4.15MB)
테스트 17 〉 통과 (0.01ms, 4.19MB)
테스트 18 〉 통과 (0.01ms, 4.2MB)

효율성 테스트

테스트 1 〉 통과 (0.01ms, 3.82MB)
테스트 2 〉 통과 (0.01ms, 3.75MB)
테스트 3 〉 통과 (0.01ms, 3.88MB)
테스트 4 〉 통과 (0.01ms, 3.85MB)
테스트 5 〉 통과 (0.01ms, 3.86MB)
테스트 6 〉 통과 (0.01ms, 3.8MB)
테스트 7 〉 통과 (0.01ms, 3.81MB)
테스트 8 〉 통과 (0.01ms, 4MB)
테스트 9 〉 통과 (0.01ms, 3.89MB)
테스트 10 〉 통과 (0.01ms, 3.75MB)