[프로그래머스] 점프와 순간 이동 - Python

해당 문제는 역순으로 생각하는 것이 키 포인트다. 마지막 예제 5000을 예시로 들면,

5000 -> 2500 -> 1250 -> 625 -> 624 -> 312 -> 156 -> 78 -> 39 -> 38 -> 19 -> 18 -> 9 -> 8 -> 4 -> 2 -> 1 -> 0

굵은 숫자를 보면, 1번씩 이동해야되는 경우가 발생한다. 즉, 나누어서 2로 떨어지지 않으면 K칸을 점프해야 된다는 것이다.

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