파이썬 알고리즘-115 (프로그래머스) 점프와 순간이동

코드

def solution(n):
    ch=[0]*(n+1)
    ch[1]=1
    for i in range(1,n+1):
        if ch[i]==0:
            if i%2==0:
                ch[i]=ch[i//2]
            else:
                ch[i]=ch[i-1]+1
            while i*2<=n:
                ch[i*2]=ch[i]
                i*=2
        if ch[-1]!=0:
            return ch[-1]
# 굳이 이렇게 풀 필요 없이 2로 나눈 나머지를 세는 방법으로 하면 더 빠르다
# 게다가 이 방식은 반복문이 중첩되어 효율성 테스트에서 실패한 방식

다른 사람의 풀이

# n을 계속 2로 나누어서 나누어 떨어지지 않을 때만 cnt+1을 해준다.
def solution(n):
    cnt = 0
    while n > 0:
        q, r = divmod(n, 2)
        n = q
        if r != 0:
            cnt += 1
    return cnt
    
# 위의 방식은 결국 어떤 숫자를 이진법으로 만드는 방식과 같고
# cnt 개수는 이진법으로 만든 숫자에서 1의 개수와도 같으므로 다음과 같이 풀 수도 있다.

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