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

 

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

처음엔 BFS로 풀었는데 실패. (시간초과 발생) 하였다. 그말은 즉, 바로 답을 찾을 수 있는 로직이 있다는 의미이다. 

 

해결 방법

숫자n이 만약 2로나누어 떨어진다면, n/2 지점에서 순간이동을 할 수 있다는 의미이다. 

만약 나누어 떨어지지 않는다면, 한칸을 이동해서 n-1 로 이동하고 / 2 를 시도한다. 

이 방법을 계속하면서, 2로 나누어 떨어지지 않는 상황이 몇번 나오는지 확인해본다.

 

#include <iostream>
using namespace std;

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