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

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

프로그래머스

---

나의 풀이

• n이 홀수라면 ans에 1을 더하고 n // 2를 해준다.
• n // 2한 값이 홀수라면 ans에 1을 더하고 n // 2해준다.
• 이를 반복하다보면 아래와 같이 규칙을 발견할 수 있다.
• 이를 재귀용법으로 구현함

def solution(n):
    ans = 0
    n = n

    return cnt(n, ans)

def cnt(n, ans):
    if n == 1:
        ans += 1
        return ans

    if n % 2 == 1:
        ans += 1
        n = n // 2
        return cnt(n, ans)
    else:
        n = n // 2
        return cnt(n, ans)

함수는 ans를 누적해줘야해서 2개 만듦

---

다른 사람의 풀이

재귀용법을 쓰지 않고 푼것이 더 빠른 것을 볼 수 있었다.

재귀용법을 쓰면 무조건 더 빠르게 풀 것이라고 생각하는 경향이 있는데 고쳐야겠다

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

def solution(n):
    return bin(n).count('1')

이진법 풀이도 있다