[C++] Programmers | 점프와 순간이동

점프와 순간이동

프로그래머스

---

✍🏻 풀이

문제에 제시된 이동 방식은 두 가지가 있다.

1. K칸 앞으로 점프 ➡️ 건전지 K만큼 소모
2. 현재 위치 * 2로 순간이동 ➡️ 건전지 소모 X

구해야 하는 값은 '건전지 사용량의 최솟값'이기 때문에 최대한 건전지 소모가 없어야 한다.

따라서 순간이동을 최대로 해야한다.

 

문제를 간단하게 하기 위해 N부터 0까지 거꾸로 이동한다고 생각하자.

 

N부터 시작하여

2로 나누어 떨어지면) 순간이동

2로 나누어 떨어지지 않으면) 1만큼 뒤로 점프

를 하면 건전지 사용량을 최소로 한 경로를 찾을 수 있다.

---

✅ Accept Code

// programmers week5-1
// 점프와 순간 이동

#include <bits/stdc++.h>

using namespace std;

int solution(int n) {
    int ans = 0;

    while (n) {
        if (n % 2 == 0) n /= 2;
        else {
            n -= 1;
            ans++;
        }
    }
    return ans;
}