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

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

프로그래머스

• 알고리즘 분류 : 구현, 수학
• 코드

#include <iostream>
using namespace std;

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

• 문제 해설

혼자서 풀리지 않아서 결국 해설을 참고했다. 큰 문제해결 방법에서 작은 문제를 해결하는 방법으로 생각하니 쉬운 문제였다.

거리가 100일 때 50만큼 갔다고 하면 순간이동으로 100까지 도달할 수 있다.

50까지 갈려면 마찬가지로  25까지 건전지를 사용하여 점프로하고 나머지는 순간이동으로 이동한다.

25까지 가는 것은 12.5로 나누어떨어지지 않아서 바로 절반은 건전지, 나머지 순간이동이 불가능하다. 따라서 한번은 점프로하고 나머지 24를 점프와 순간이동을 하면된다.

따라서 구현을 하면 거리 n에서 시작해서 짝수일 경우 2로 나누고 홀수일 경우 카운트하고 1을 빼준후 나누는 것을 거리가 0이 될때까지 반복하면 된다.