[프로그래머스/Level 2] 점프와 순간 이동 (C++)

programmers.co.kr/learn/courses/30/lessons/12980

코딩테스트 연습 - 점프와 순간 이동

 

풀이

처음에 BFS로 풀었는데, 숫자가 최대 10억까지 이므로 절대 BFS로 효율성 검사를 통과할 수 없다.

해결방법은 n에서 0으로 가는 것을 생각하면 되는데, 최대한 2를 나눌수록 0에 가까워지므로 2로 나누면서, 2로 나눈 나머지가 1인 경우에만 res를 해준다. (점프한 경우이므로)  

 

전체 코드

#include <iostream>
using namespace std;

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