Jump and teleport

해당 문제는 여기에서 확인하실 수 있습니다.

문제를 해결하기 위해서는 주어진 거리 N을 이동할 때 최소한의 건전지 사용량을 찾는 것이 핵심입니다. 점프는 건전지를 소비하므로, 이를 최소화하는 방법을 찾아야 합니다. 먼저, 문제에서 제공된 힌트는 순간이동을 사용하는 것이 건전지를 아끼는 데 매우 유리하다는 점입니다. 순간이동은 현재까지 이동한 거리를 두 배로 늘릴 수 있지만, 건전지를 소모하지 않습니다. 반면, 점프는 한 번에 K만큼 이동할 수 있으나 그만큼 건전지를 소모하게 됩니다. 이를 고려하여, 순간이동을 최대한 많이 사용하고 점프는 필요한 경우에만 최소한으로 사용해야 합니다.

해결 방법은 주어진 거리 N이 짝수일 경우, 이를 2로 나눠 순간이동을 하는 방식입니다. 이때 건전지를 소모하지 않으므로 계속해서 N을 줄여나갈 수 있습니다. 그러나 N이 홀수일 경우에는 점프를 해야 하므로 1을 빼고 건전지를 1만큼 사용한 후, 다시 N을 2로 나눕니다. 이 과정을 N이 0이 될 때까지 반복합니다.

이렇게 하면 결국 N을 이진수로 표현했을 때, 1의 개수가 최소한의 건전지 사용량이 된다는 사실을 알 수 있습니다.

import java.util.*;

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

    // n이 0이 될 때까지 반복
    while (n > 0) {
      // n이 짝수일 경우 순간이동 (건전지 사용량 증가 X)
      if (n % 2 == 0) {
        n /= 2;
      } 
      // n이 홀수일 경우 1칸 점프 (건전지 사용량 1 증가)
      else {
        n -= 1;
        ans++;
      }
    }

    // 최종적으로 사용된 건전지 사용량 반환
    return ans;
  }
}