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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 점프와 순간 이동

새로 알게된 것들

어떤 수를 2로 나눈 나머지들의 합은 어떤 수를 이진수를 변환 후 이진수의 1의 개수와 같다는 것을 이전에도 본적이 있지만 이 문제를 풀때는 생각하지 못했다.

풀이

어떤 숫자 K로 2배 이동하여 가기 위해선 K / 2에서 2배를 하면 되는데 그럼 K / 2로 2배 이동하여 가기 위해선 K / 4에서 2배를 하면 된다. 이렇게 생각을 하다 보니 다음과 같은 풀이가 떠올랐다.

최대한 현재 온 거리보다 2배씩 이동하는 것이 건전지 사용량이 덜 들기 때문에 K칸을 2로 나누고 나누어지지 않을 때는 1을 빼고 다시 2를 나누는 과정을 반복한다. 이런 과정을 반복하면 거리의 2배를 최대한으로 사용하여 K칸을 이동할 수 있다.

코드

def solution(n):
    ans = 1
    while n != 1:
        if n % 2 == 0:
            pass
        else:
            ans += 1
        n //= 2
    return ans

느낀점

풀이법이 바로 생각이 나지 않아 코드는 짧지만 빠르게 풀지 못했다. 다시 한번 말하지만 문제를 풀때 좁게 보지말고 넓게 보자.