[Python] 프로그래머스 12980. 점프와 순간이동 (Lv.2)

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

프로그래머스

 

0에서 n으로 가는것 보다 거꾸로 n에서 0으로 오는 방법을 생각하면 쉽게 풀리는 문제입니다. 탐욕법(Greedy) 풀이라고 봐도 되겠네요.

 

어떤 위치 x에서 0으로 갈때 x가 2의 배수라면 배터리를 쓰지 않고 x / 2로 순간이동할 수 있습니다. 순간이동을 하면 배터리를 쓰지 않기 때문에 순간이동이 가능할 때는 무조건 순간이동을 하는게 유리합니다. 따라서 n이 0이 될 때까지 2의 배수라면 /2를, 2의 배수가 아니라면(홀수라면) 1을 빼서 짝수로 만들며 풀이하면 됩니다.

 

def solution(n):
    a = 0
    
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
            a += 1
    return a