프로그래머스 | 점프와 순간 이동 [파이썬 python]

프로그래머스

 
코드

def solution(n):
    answer = 0
    while n > 0:
        if n % 2 == 0: # 짝수이면 //2
            n = n // 2
        else: # 홀수이면 -1
            n = n - 1
            answer += 1 # -1 하는 횟수가 답
    
    return answer

문제를 보자마자 그리디 유형이 아닐까.. 하고 생각했다.
순간이동의 횟수를 최대로 해야 건전지 사용량이 최소가 될 수 있기 때문에 어떻게 순간이동의 횟수를 최대화하느냐가 관건이었다.
하지만 주어진 예시를 봐도 기준을 잘 모르겠어서 힌트를 찾아 인터넷 세상을 돌아다녔고, 홀짝으로 접근하면 된다는 것을 알게 되었다.
0에서 n까지가 아닌 거꾸로 n에서 0으로 가는 방법을 생각하면 쉽게 도출해 낼 수 있다.
 
먼저, 문제에서 주어진 n=5, n=6인 경우를 각각 살펴보면 다음과 같다.
5 → 4 → 2 → 1 → 0 (2)

• 5
• 5 -1 = 4
• 4 // 2 = 2
• 2 // 2 = 1
• 1 - 1 = 0

6 → 3 → 2 → 1 → 0 (2)

• 6
• 6 // 2 = 3
• 3 - 1 = 2
• 2 // 2 = 1
• 1 - 1 = 0

n이 홀수일 때 n = n-1을 하고, n이 짝수일 때 n = n // 2를 n이 0이 될 때까지 해주는 것을 알 수 있다.
두 예시에서 -1을 한 횟수(=점프)는 모두 2번이며, 문제에서 K칸을 점프하면 K만큼의 건전지 사용량이 든다고 했다.
따라서, n=5일 때 건전지 사용량은 2, n=6일 때 건전지 사용량은 2이다.
 

다른 사람의 풀이

def solution(n):
    return bin(n).count('1') # 이진수 n에서 1의 개수

이 코드를 처음 봤을 때 뭐지..? 이게 어떻게 되는 거지..? 어떻게 이걸 바로 생각해 내지?라고 생각했다.
어떤 사람이 순간이동이 시프트(shift)라고 한 것을 보고 풀이를 찾아보았으나 구체적인 설명이 없어서 내가 직접 하나씩 이진수를 작성해 보았다.

* 시프트 연산: 한 자리씩 앞으로 이동 ex) 001 -> 010, 100 -> 1000
 

0 → 1 → 2 → 4 → 5 (2)

• 0 = 000
• 0 + 1 = 1 = 001
• 1 × 2 = 2 = 010
• 2 × 2 = 4 = 100
• 4 + 1 = 5 = 101

n=5일 때 이진수만 보면 +1이 될 때는 이진수에 1씩 더해주는 것을 알 수 있고, ×2를 할 때는 한 자리씩 시프트연산을 하는 것을 알 수 있다. 
0 → 1 → 2 → 3 → 6 (2)

• 0 = 000
• 0 + 1 = 1 = 001
• 1 × 2 = 2 = 010
• 2 +1 = 3 = 011
• 3 × 2 = 6 = 110

n=6일 때도 마찬가지로 +1을 할 때는 이진수에 +1을, ×2를 할 때는 한 자리씩 시프트연산을 해준다.
 
결국 +1을 한 횟수 = 주어진 n에서 1의 개수임을 알 수 있다.
시프트 연산은 1의 개수에는 어떠한 영향도 주지 않으므로 100과 1000에서 1의 개수는 같다.
반면, +1을 할 때마다 1의 개수가 증가하게 된다.
 
따라서, 주어진 n에서 1의 개수를 세면 문제에서 구하고자 하는 건전지 사용량이 된다.