[프로그래머스] 점프와 순간 이동 - python

점프와 순간 이동

문제 설명

아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

제한사항

• 숫자 N: 1 이상 10억 이하의 자연수
• 숫자 K: 1 이상의 자연수

풀이

처음에는 bottom-up dp를 생각했다.

• 만약에 i가 2로 나눠떨어지면 i//2 와 i-1 중에 작은 거를 선택해서 + 1
• 홀수면 i -1 +1

그런데 입력값이 10억이므로 O(n)으로 풀면 시간 초과가 날 것 같았고 O(logn)으로 풀어야했다. 그래서 이진 탐색인가 싶어서 혼란스러웠다.

결론적으로 top-down 방식으로 접근하면 O(logN)으로 해결할 수 있었다.

• N에서 2로 나눠떨어지는 곳은 순간이동으로 갈 수 있다.
• 나눠떨어지지 않으면 점프를 해야하므로 -1해주고 건전지 소모량에 +1해준다.
• n을 2로 나눠가면서 0이 될 때 까지 반복한다.

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

이렇게 간단한 거였다니

다른 사람 풀이

이진법을 이용하는 방법이 있었다....

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