[programers] 프로그래머스(파이썬) : 점프와 순간 이동

문제

코딩테스트 연습 - 점프와 순간 이동

알고리즘

- 0부터 n까지 가는 최소 비용은 n부터 0까지 가는 최소 비용과 같다.

- n이 짝수라면 비용이 들지 않는다.(*2 이기 때문에)

- n이 홀수라면 한 칸 점프한다.

- n이 2보다 클 때까지만 반복한다.

- 반복문이 끝나고 비용을 출력한다.

코드

def solution(n):
    ans = 1
    
    # n부터 0까지 가는 최소 비용 구하기
    while n > 2:
    	# n이 짝수라면 비용이 들지 않는다.
        if n % 2 == 0:
            n /= 2
        
        # n이 홀수라면 비용이 든다.
        # 한칸 점프
        else:
            ans += 1
            n -= 1
    
    return ans

 

다른 사람 풀이

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

결국 2진수의 1의 개수만큼 비용이 드는 것으로 위 코드로 해결 가능하다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법