점프와 순간 이동
def solution(n):
return bin(n).count('1')
풀이
순간이동 : 현재까지 이동해온 거리 * 2
일단 무조건 처음에는 점프를 뛰어야합니다. 그래야 순간이동으로 갈 수 있습니다. 그리고 순간이동을 하면 할수록 거리는 2배씩 늘어나니 굳이 점프는 1칸 이상 뛸 필요가 없습니다. 왜냐하면 목적은 점프를 최소한으로 쓰는 것이기 때문입니다. 그러면 도달해야하는 목적지가 N 일 때 이런식으로 식을 세울 수 있습니다.
\(2^x + 2^y + \cdots + 2^z = N\)
2의 제곱승들을 합해서 N을 만드는데 2의 제곱승을 몇번썼냐? 이겁니다. 그런데 2의 제곱승의 합으로 어떤 수를 만든다? 바로 이진법 오우쒯!!
그래서 이진법으로 바꾼다음에 1의 갯수를 세어주면 됩니다.