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

문제의 이해

1. 상황
건전지로 작동하는 아이언 슈트가 있다. 기능은 아래 두 개

• 한 번에 K 칸을 앞으로 점프 => 건전지 사용량 K
• (현재까지 온 거리)x2에 해당 위치로 순간이동 => 건전지 사용량 0

2. 하고 싶은 거

N만큼 떨어져 있는 장소로 가려고 함
건전지를 가장 최소로 사용하려 함

3. 얻어야 하는 거

건전지를 가장 최소로 사용하며 도착하면 드는 건전지 사용량

4. 제한 사항

숫자 N : 1 <= N <= 10억 의 자연수
숫자 K : 1 <= K 의 자연수

문제 해결 아이디어

1. N에서 절반씩 줄이면서 가는게 좋을까?
   1에서 숫자를 늘리며 뻗어 나가는게 좋을까?

2. DP 유형 문제인 듯 하다.

예시1) N이 5인 경우
[0][1][2][3][4][5]
[0][1][1][ ][1][2]
1. 1칸 점프 : 1
2. 순간이동 : 2
3. 순간이동 : 4
4. 1칸 점프 : 5

여기서 사용한 건전지의 양은 1+1=2

예시3) N이 5000
1. 5000 => 2500
2. 2500 -> 1250
3. 1250 -> 625
4. 625 -> 624 : 1
5. 624 -> 312
6. 312 -> 156
7. 156 -> 78
8. 78 -> 39
9. 39 -> 38 : 1
10. 38 -> 19
11. 19 -> 18 : 1
12. 18 -> 9
13. 9 -> 8 : 1
14. 8 -> 4
15. 4 -> 2
16. 2 -> 1
17. 1 -> 0 : 1

이런 식으로 거꾸로 /2 또는 -1 하면서 탐색해나간다.

내 코드

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

    return ans

다른 사람의 코드

다른 사람들의 코드도 봤는데 머리가 띵해졌다
binary를 사용할 생각을 하다니..
만약 이게 실전 코딩테스트였다면 난 이진법을 생각해냈어도 bin().count()를 생각해내지 못할 것 같다..
어케 이진수에 count를 할 수 있냐고.. 애초에도 생각해낼 수 없을 듯ㅋㅋㅋㅎㅎ

숫자에 bin 함수를 때리면 0b100, 0b10101011001 이런식으로 String이 반환된다!!!! 잊지 말길

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