[프로그래머스 lv2] 점프와 순간이동 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

0에서 n까지 이동할 수 있는 방법은 두가지이다.

첫째, 현재 위치에서 2배 위치로 이동하는 것(순간이동, 건전지 소모 X)

둘째, K 만큼 점프하는 것(점프, K만큼의 건전지 소모 O)

 

방향을 뒤집어 n에서 0까지 이동한다고 생각해보자.

현재의 위치가 짝수이면 무조건 n/2 위치로 순간 이동을 하는 것이 유리하다. 순간이동은 건전지 소모가 없기 떄문이다.

반면, 현재 위치가 홀수이면 n/2 위치로 순간 이동을 할 수 없으므로 무조건 건전지를 1 소모해야 한다.

 

따라서, 반복문 내에서 n이 홀수이면 n을 1줄이면서 건전지 소모량을 1 늘리고, 짝수이면 n을 2로 나누어주자.

n이 0이 되었을 때 총 건전지 소모량을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(int n) {
    
    int cnt = 0;
    while (n) {
        if (n%2) {
            n--;
            cnt++;
        }
        else n /= 2;
    }
    return cnt;
}