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

1.문제 링크

점프와 순간 이동

2. 풀이 전 계획과 생각

• 2를 곱할 수 있을 때까지 곱하고 나머지는 점프로 처리하기

3. 풀이

#include <iostream>
using namespace std;

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

    while(1){
        if(n==1) {
            ans++;
            break;
        }

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

    return ans;
}

n이 만약 짝수면 n을 2로 나누고, n이 홀수면 ans를 1증가하고 (n-1)/2를 한다. 만약 n이 1이면 ans를 1증가시키고 ans를 반환한다.

4. 풀이하면서 고민했던 점

• 처음 생각한 것처럼 풀었더니 오답이 나옴 처음에 2로 갈 수 있을 만큼 간 후 나머지는 점프로 처리했다. 하지만 이 방식은 매우 비효율적인 방식이다. 예로들어 n이 30일 때 1->2->4->8->16까지 한 다음 14를 점프해야 한다.

5. 문제를 풀고 알게된 개념 및 소감