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

문제 링크

점프와 순간 이동

풀이

처음에는 DP문제인가 싶어서 주석처럼 풀었다가 시간, 메모리 초과가 나길래 다시 풀었음

1. 순간 이동을 할 때는 건전지를 안쓰니까 이걸 이용해 반대로 생각한다.
2. 거리가 1이 될 때까지 반복하는데(거꾸로 계산하기), n을 2로 나누었을 때 나머지가 있다면(홀수라면) 어차피 점프 한 번은 해주어야함. 그래서 ans++를 해준다.
3. 나머지가 없다면 점프 할 필요가 없으니 그냥 다음 계산을 해준다.

코드

#include <iostream>
#include <vector>
using namespace std;

int solution(int n)
{
    int ans = 0;
    
    /*vector<int> v(n+1);
    
    v[0] = 0;
    v[1] = 1;
    
    if(n==1) return 1;
    
    for(int i=2;i<=n;i++)
    {
        if(i%2==0) { // 짝수
            v[i] = v[i-1]+1 < v[i/2] ? v[i-1]+1 : v[i/2];
        }
        else { // 홀수
            v[i] = v[i-1]+1;
        }
        
    }
    
    ans = v[n];*/
    
    while(n>=1)
    {
        if(n%2==1) {
            ans++;
        }
        n/=2;
    }

    return ans;
}