[Programmers - S/W coding 2018] 점프와 순간이동 (cpp / python)

점프와 순간이동

프로그래머스

문제 설명

점프 : 1칸 이동 -> 1번당 베터리 1 소모

순간이동 : 현재까지 온 거리 $\times$ 2 위치로 이동 -> 1번당 베터리 소모 X

즉, 순간이동을 최대한 많이 해서 도착지점까지 도달하는 방법을 구하는 문제

Key Point 는 순간이동은 현재위치 $\times$ 2 까지 움직일 수 있다는 것이다.    

 

$$  
\require{enclose}
\begin{array}{r}
0\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(J)\\
1 \,\,\dots \,\,\,\,\,\,\,0(T)\\[-3pt] 
2 \enclose{longdiv}{\,\,\,2} \,\,\,\dots 1 (T,J) \\[-3pt] 
2 \enclose{longdiv}{\,\,\,5} \,\,\,\dots \,\,\,\,\,\, 0 (T) \\[-3pt] 
2 \enclose{longdiv}{10} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,
\end{array}
$$  

 

0에서 Jump

1에서 Teleport

2에서 Teleport

4에서 Jump

5에서 Teleport

10 도착

결국 도착지점인 N의 이진수로 나타네어 1의 개수를 세어주는 문제다.

문제 풀이

소스코드 : C++

1. 주어진 N 을 2로 계속해서 나누어 가며 나머지가 생길 때 마다 answer++ 해준다.
2. 여기서 나머지를 뺄 필요는 없는게 어짜피 내림 계산을 한다.

#include <iostream>
#include<bitset>
using namespace std;

int solution(int n){
    int answer = 0;
    while (n != 0) {
        if (n % 2 == 1)answer++;
        n /= 2;
    }
    return answer;
}

소스코드 : Python

와우.. 해당 숫자의 이진수의 1의 개수를 셀 수 있다.

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