[코테] 수학 - 점프와 순간 이동[프로그래머스]

문제

출처: 프로그래머스 - 점프와 순간 이동

풀이

0에서 출발하여 도착지점까지 최소한의 건전지를 사용하며 순간 이동으로 도착할 수 있는지 묻는 문제다.
0에서 출발하는 것을 계산하게 되면 많은 경우의 수가 생기기에, 역으로 도착지점부터 반씩(나누기 2)를 하여 순간 이동 및 건전지를 써서 0에 도착하는지 계산하면 쉽게 풀린다.
도착지점 n에서 역으로 순간 이동을 하는 지점은 n에서 2를 나눈 지점으로써 나누었을 때 나머지가 0이 아니라면 건전지를 1을 쓰도록 한다. 이것을 n이 0이 될 때까지 계속 반복한다.

코드

def solution(n):
    ans = 0 # 건전지 사용량
    while n > 0: # 도착점 0이 될 때까지 몫을 구한다.
        if n % 2 != 0: # 0이 아니라면 도착할 수 없는 실수의 범위가 됨으로 건전지를 써서 나머지가 0이 되도록 해주고 건전지 소모를 1 올려준다.
            ans += 1
        n //= 2 # 2를 나누어 n의 몫을 계속 구한다.

    return ans