[알고리즘] 점프와 순간이동

접근 방식

• 처음에는 이전에 풀었던 BFS 와 비슷한 유형인줄 알고 풀려고 했다. 전혀아니었다
• 뭔가 BFS 로 전체 탐색하기엔 최소 거리를 구하는것도 아니고, 입력 숫자도 최대 10억으로 큰 숫자였다.
• 그래서 두번째로 이분탐색을 이용한 결정문제로 풀면되지 않을까 생각이 들었다.
• 그래서 만약 K개 이상의 배터리를 사용해서 목적지에 도달할수 있는지를 판별하려고 하다가, 이것도 결국엔 BFS 형식으로 가게될것같았다.
• 그래서 고민고민하다가, 순간이동을 가장 많이 하게끔 하는 경우에 공식이 생기지 않을까 싶었다.
• 만약에 목적지가 5 이면 5 : (- 1) => (/ 2) => (/ 2) => (- 1): 0 으로
• top-down 방식으로 생각하면 현재 탐색중인 숫자가 홀수면 -1 을 빼고 짝수면 2 로 나눈 후 -1 을 한 개수를 세면 가장 -1 을 적게 해서 만들수 있지 않나 싶었다.
• 이렇게 접근하였더니 모든 케이스가 통과 되었다..

#include <iostream>
using namespace std;

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