[Programmers] L2. 점프와 순간 이동 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

💡 짝수와 홀수를 구분하고, 순간이동은 2배만큼 하므로 2로 나누기

 

N이 6이라고 할 때, 다음 그림과 같다. 파란색 숫자는 순간이동을 한 위치이다.

• 순간이동을 할 때 2의 배수만큼 움직이므로 2로 나누는데, 이때 홀수와 짝수를 구분한다.
• 홀수이면 -1 을 한 후에 2로 나눠야 하는데, 이 과정이 jump를 한 것과 같다.
• 따라서 홀수일 때만 -1 을 해주고 jump 횟수를 카운트 해준다.

Solution

def solution(n):
    ans = 0
    while n > 0:
        if n % 2 != 0:
            n -= 1  # jump
            ans += 1
        n //= 2

    return ans

 

📌 짝수와 홀수로 구분하는 이유

• 짝수 위치에서는 순간이동이 가능하므로 건전지 사용량을 줄일 수 있다. 이 경우, 현재 위치를 절반 거리로 나눈 위치에서 순간이동을 통해 현재 위치로 올 수 있었던 셈이다.
• 반면 홀수 위치에서는 현재 위치로 오기 위해 마지막에 반드시 1칸 점프가 필요하다. 이때 건전지 1을 소모하게 되며, 이후에는 짝수로 만들어 순간이동을 활용할 수 있다.

📌 2로 나누는 이유

• 순간이동을 할 때마다 이동 거리가 현재 위치의 2배가 되므로, 거리를 줄이는 데에도 2로 나누며 거꾸로 역추적하게 된다.
• 매 단계에서 N을 2로 나누는 작업은, 순간이동 가능한 짝수 거리에서 최대한 순간이동을 하도록 돕는다.

---

👩‍💻 회고

다른 풀이 보니 이렇게도 풀던데,, 진짜 천재인 것 같다. 대체 어떻게 이렇게 풀 생각을 했는지 감탄을 안 할 수 없었다.

def solution(n):
    return bin(n).count('1')

 

 

이 코드에서는 bin(n).count('1')를 통해 2진법에서 '1'의 개수를 세어, 이동에 필요한 최소한의 건전지 사용량을 구하고 있다. 이 방법이 가능한 이유는 아이언 슈트가 이동할 때, 점프해야 하는 횟수가 '1'의 개수와 일치하기 때문이다.  

---