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

문제 링크

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

코딩테스트 연습 - 점프와 순간 이동

풀이 

- bfs로 시도했지만 규칙을 찾아서 푸는 구현 문제... 

 

- 거꾸로 이동하면서 

n이 2의 배수이면 건전지를 사용하지 않고 순간이동을 통해 이동할 수 있으므로 n // 2 로 이동 

n을 2로 나누었을 때 나머지가 1이면 건전지를 사용해서 한 칸 이동후 n //2 로 이동하므로, ans + 1 

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