[프로그래머스] (Java) 점프와 순간이동 - 그리디, 비트마스크

 

 

📑 1. 문제설명

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

1. 문제 요약

 

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

---

💡 2. 풀이과정

솔직히 10분 넘게 생각해봤는데 

어떻게 구현 해야 할 지 1도 감이 안 와서 남의 코드 보고 풀었다. 
그리고 홀수 판별식 n % 2 == 1 를 이렇게도 쓸 수 있다. (n & 1) == 1

---

👨‍💻 3. 정답코드

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)를 세는 것이다.

 

여기서 어려운 부분이 있어서 정리해보는 시간을 갖는다. 

---

"역추적"이라는 말의 의미

우리가 실제 게임에서 이동하는 건 0 → N 이다. 여기 코드에서는 거꾸로 N → 0 으로 계산하고 있다. 

즉, n이 현재 위치라고 하면,

• 짝수라면 → 직전에 순간이동해서 왔음 → /2 해주면 된다.
• 홀수라면 → 직전에 점프해서 왔음 → -1 해주면 돼

---

왜 홀수면 "1칸 점프" 역추적인가?

예를 들어 n=5일 때를 보자.

• 앞으로 순간이동은 ×2밖에 안 된다.
• 그러면 어떤 수에 ×2 해서 5가 될 수 있을까? → 없다는 결론이 나온다 왜냐하면 짝수만 가능하잖아...
• 즉, 5라는 위치에 오기 위해서는 직전에 반드시 1칸 점프를 했어야만 한다는 결론에 도달하게 된다.

즉, n=5 → n=4(점프 -1) → 여기서야 순간이동이 가능하다.
그래서 역추적할 때 n -= 1을 하고, 그 순간 배터리++ 가 점프 비용으로 1 증가하는 것이다.

n=5 (홀수) → 점프1칸 했구나 → n=4, battery=1 // 여기서 1증가
n=4 (짝수) → 순간이동 했구나 → n=2, battery=1
n=2 (짝수) → 순간이동 했구나 → n=1, battery=1
n=1 (홀수) → 점프1칸 했구나 → n=0, battery=2 // 여기서 또 1 증가
결과 → 최소 배터리 = 2

 

놀랍게도 이걸 한 줄로 줄이는 방법이 있다.

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

 

---

🐦 4.  TMI

 

홀수판별식

보통은 홀수 판별식을 n % 2 == 1 이렇게 쓴다. 2로 나눴을 때 나머지가 1이면 홀수이기 때문이다.

그런데 비트로도 표현할 수 있다. (n & 1) == 1  이렇게도 가능하다.

이진수에서 맨 오른쪽 마지막 비트를 LSB라고 한다. Least Significant Bit이다.

10진수	n진수	LSB
4	100	0
5	101	1
6	110	0
7	111	1

• 마지막 비트가 0 → 짝수
• 마지막 비트가 1 → 홀수

이게 되는 이유는 1은 이진수로0001이다. n & 1 이라는 것은 다른 의미로 n의 마지막 비트만 남긴다는 뜻이다.

• 마지막 비트가 1 → (n & 1) == 1 → 홀수
• 마지막 비트가 0 → (n & 1) == 0 → 짝수