Skip to main content

[Java] 12980 점프와 순간 이동

📝 점프와 순간 이동

1. 문제 요약

  • K칸 점프 → K만큼 건전지 소비
  • 현재까지의 거리 * 2로 순간이동 → 건전지 소비 X
  • 거리 n까지 이동하는데 드는 최소 건전지의 개수 리턴
  • 아래 예시에서 방법 3이 가장 적은 건전지 소비

0 (1).png

2. 정답코드

class Solution {
    public int solution(int n) {
        int battery = 0;
        while (n > 0) {
            if ((n & 1) == 0) { // 짝수면 순간이동 역추적
                n >>= 1;
            } else {            // 홀수면 점프 1칸 역추적
                n -= 1;
                battery++;
            }
        }
        return battery;
    }
}

거꾸로 생각하면 된다. N을 0으로 줄여간다고 생각하자.

  • N이 짝수일 때
    → 직전에 무조건 순간이동으로 왔음
    → 따라서 N /= 2 (배터리 소모 없음)
  • N이 홀수일 때
    → 직전에 반드시 앞으로 1칸 점프를 했어야 함
    → 따라서 N -= 1 (배터리 +1)

이 과정을 N이 0이 될 때까지 반복하면 홀수였던 횟수 = 점프 횟수 = 배터리 소모량이 된다.
즉, 이 코드는 N을 이진수로 쭉 읽으면서 1이 나올 때마다 점프 횟수(battery)를 세는 것이다.

이걸 한 줄로 줄이는 방법이 있다.

class Solution {
    public int solution(int n) {
        return Integer.bitCount(n); // n의 이진수에서 1의 개수
    }
}

이진수로 N을 표현했을 때,

  • 1 → 홀수 → 점프 필요 (배터리 +1)
  • 0 → 짝수 → 순간이동 (배터리 +0)
  • 따라서 N의 이진수에서 1의 개수 = 최소 배터리 소모량이 된다.

예시) N = 5

  • 이진수 = 101
  • 1이 2개 있음 → 배터리 2 소모
  • 실제 과정: 5(홀수 → -1, 배터리1) → 4(짝수 → /2) → 2(짝수 → /2) → 1(홀수 → -1, 배터리1) → 0
  • 최종 배터리 = 2

3. 오답 / 어려웠던 점
솔직히 어떻게 해야 할 지 1도 감이 안 와서 남의 코드 보고 풀었따다 ㅋ
다음부터는 내가 혼자서 풀면 되니까 ㅋㅋ
그리고 홀수 판별식 n % 2 == 1 를 이렇게도 쓸 수 있다. (n & 1) == 1



Back to top