(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 점프와 순간이동

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

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

진수활용 문제였습니다.

 

풀이방법

*가장 먼저 떠올릴 수 있는 풀이방법은 bfs나 다익스트라이지만 n이 10억이므로 시간복잡도가 높아집니다. 따라서 다른 방식을 생각해야합니다. 

 점프를 한 것은 현재자리에서 1칸을 움직인 것에 해당하며 순간 이동을 하게되면 현재자리에서 *2를 하므로 다음 자리로 넘어가게 됩니다. 이는 이진수의 속성에 대입해볼 수 있습니다. 구현은 정말 쉽지만 생각을 확장해야하는 문제입니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

int solution(int n){
    int ans = 0;
    while(n){
        ans += n % 2;
        n /= 2;
    }
    return ans;
}