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

📝 문제

💡 풀이

🔍 처음엔 그래프 탐색 문제거나 다익스트라인줄 알았다. 그런데 K칸이라는게 정해져 있지 않고 1~무한대까지 가능해서 이렇게 찾으면 시간 초과가 날 거 같았다

🔍 생각해보면 결국 현재까지 온 칸의 2배를 하면 N칸에 도달할 수도 있다는 말이 된다. N에서부터 2로 나눠서 계속 내려오다보니 홀수가 되는 칸에서는 1칸씩 점프를 해야 했고 짝수는 그대로 순간이동해서 계속 내려올 수 있었다

N부터 2로 나눠서 1이 될때까지 만들되, 중간에 홀수가 나오면 건전지 +1

def solution(n):
    ans = 1
    
    while n>1:
        ans += n%2
        n //= 2

    return ans