점프와 순간 이동

문제

어떤 사람이 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있습니다. 순간이동을 하면 건전지 사용량이 줄지 않지만, K 칸을 앞으로 점프하면 K 만큼의 건전지 사용량이 듭니다. 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 반환하는 프로그램을 작성하는 문제입니다.

• 입력: 도착해야 할 거리 N (1 이상 10억 이하의 자연수)
• 출력: 사용해야 하는 건전지 사용량의 최솟값

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

풀이 1: 거꾸로 이동하기 (Top-Down 탐욕법)

작성해주신 코드처럼, 출발지(0)에서 N으로 가는 대신 도착지(N)에서 0으로 거꾸로 돌아가는 방식을 생각하면 매우 직관적으로 풀립니다. 순간이동(x2)은 건전지가 소모되지 않으므로 최대한 많이 사용하는 것이 무조건 이득입니다.

• 역순 탐색: 목표 지점 n이 0이 될 때까지 반복합니다.
• 순간이동 역연산 (2로 나누기): 현재 위치 n이 짝수라면, 이전 위치에서 건전지 소모 없이 순간이동(x2)으로 올 수 있었던 위치입니다. 따라서 홀수가 될 때까지 계속해서 2로 나누어 줍니다 (n /= 2).
• 점프 역연산 (1 빼기): 현재 위치 n이 홀수라면, 순간이동으로 도달할 수 없는 위치입니다. 따라서 무조건 1칸을 점프해서 와야 하므로 n에서 1을 빼고(n--), 건전지 사용량(ans)을 1 증가시킵니다.
• 이 과정을 반복하면 최소한의 점프(건전지)만으로 0에 도달하는 최적의 경로를 찾을 수 있습니다.

코드 1

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = 0;
        
        while (n != 0) {
            // 짝수일 경우 건전지 소모 없이 2로 나눔 (순간이동 역연산)
            while (n % 2 == 0) {
                n /= 2;
            }
            
            // 홀수일 경우 1칸 점프한 것으로 간주 (점프 역연산)
            n--;
            ans++;
        }
        
        return ans;
    }
}

풀이 2: 2진수 변환과 비트 연산을 활용한 O(1) 최적화

이 문제의 동작 원리를 가만히 들여다보면 10진수를 2진수로 변환하는 과정과 완벽하게 일치합니다. 어떤 수 N을 2로 계속 나누면서 나머지가 1이 생길 때마다 건전지를 1씩 사용하게 되는데, 이는 곧 N을 2진수로 변환했을 때 포함된 '1'의 개수를 세는 것과 완벽히 동일한 수학적 의미를 갖습니다.

따라서 자바의 내장 함수인 Integer.bitCount()를 사용하면, 복잡한 반복문 없이 단 한 줄만으로 정답을 구할 수 있습니다.

코드 2

import java.util.*;

public class Solution {
    public int solution(int n) {
        // n의 2진수 표현에서 1의 개수가 곧 필요한 점프(건전지) 횟수
        return Integer.bitCount(n);
    }
}

알고리즘 분류

탐욕법 (Greedy), 수학 (Mathematics), 비트 조작 (Bit Manipulation)