점프와 순간 이동

코드

[ 효율성 검사 실패 코드 ]

#include <iostream>
using namespace std;

int solution(int n)
{
    long long cost = 0;
    long long ans;
    long long board[n+2];
    fill(board, board+n+2, 0);
    for(long long i=1;i<=n;i++)
    {
        if(board[i]) {
            cost = min(cost, board[i]);
            continue;
        }
        board[i] = ++cost;
        for(long long j=i*2;j<=n;j=j*2){
            if(!board[j]) board[j]=cost;
        }
    }
    ans = board[n];
    return ans;
}

• 로직
  : board판을 만들어서 에라토스테네스의 채 처럼 수를 적어나가는 방식
• 문제
  1) 시간초과ㅠㅠ
  2) 메모리 영역 초과(스택 영역)
  : 지역변수의 메모리는 스택 영역에 포함되어 스택 크기에 따라 제한이 걸리게 된다.
  그러나, 전역 변수로 사용하면 힙 영역에 포함되어 보다 큰 크기로 사용할 수 있다.

---

[ 정답 코드 ]

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans=0;
    while(n != 0){
        if(n&1) ans++;
        n = n/2;
    }
    return ans;
}

• key point!
  : 2로 나누었을 때 나머지가 1이라면 1만큼 점프를 해야하는 것을 의미
  (1과 비트연산을 사용하면 효율적)