# 프로그래머스 점프와 순간이동
# 나는 처음에 dp로 푸는건줄 알고 dp로 풀었는데 정확성테스트는 다 맞는데
# 효율성테스트에서 런타임에러 뜨고 시간초과 뜨고 그랬다.
# 보니깐 10억개의 리스트는 메모리상 안 만들어지는거 같다. n이 10억이하의 자연수라고
# 했기 때문에.... 런타임에러뜬듯. 그리고 그보다 더 큰 숫자가 쓰이면
# 너무 많은 계산을 필요로해서 시간초과 뜬거 같다.
# 그래서 다른 사람의 코드를 참고해서 했는데 나는 0, 1에서부터 시작했다고 하면 
# 이 사람의 코드는 n 부터 시작해서 짝수면 나누고 홀수면 1빼고 건전지 1을 더 사용했다고
# 했다. 나랑 생각한 방법은 거의 비슷한데 나는 모든 숫자 하나씩 다 계산한 반면에
# 정답인 코드는 n부터 나누고 빼고 하니깐 계산할 숫자가 훨씬 적어져서 시간초과가 안 뜨는듯.
# 오늘도 하나 배워갑니다.

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

print(solution(6))


# def solution(n):
#     ans = 0
#     dp = [0] * (n + 1)

#     dp[0] = 0
#     dp[1] = 1

#     for i in range(2,n+1):
#         dp[i] = dp[i//2] if i & 1 == 0 else dp[i-1] + 1
    
#     ans = dp[n]

#     return ans
