Programmers : 점프와 순간이동

풀이 요약

나눗셈 처리 (풀이 참조)

풀이 상세

1. 문제를 풀기 전 다양한 시도를 해보았다. DP는 메모리 초과 및 시간초과 때문에 안되고, 약수를 만들어, 약수에 홀수가 존재하는 경우 거리를 늘리나 예외가 있었다.

2. 정답은 나눗셈을 진행하며 홀수가 나오는 경우, 이동을 하는 것이다. 짝수인 경우에는 임의의 값 n의 거리 값은 모두 n/2, (n/2)/2, ((n/2)/2)/2 … 에 동일할 것이며, n의 값이 홀수 인 경우에는 n-1 이 짝수가 되며 (n-1)/2, ((n-1)/2)/2 … 에 동일하기 때문에 홀수마다 앞으로 점프하면 된다.

배운점

• 안 풀리는 문제들이 있다.

오답코드 - DP

최대 10억개를 저장해야하는데 메모리 초과 나옴

#include <iostream>
using namespace std;

int solution(int n)
{
    int dp[n+1];
    dp[1] = 1, dp[2]=1;
    for(int i=3; i<=n; i++) {
        dp[i] = !(i%2) ? dp[i/2] : dp[i-1]+1;
    }
  
    return dp[n];
}

오답코드 약수로 구분하기

7의 경우 1,7 밖에 없지만 결과값은 3이다.

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

int solution(int n)
{
    int ans = 0;
    for(int i=1; i<=sqrt(n); i++) {
        if(n%i==0) {
          if(i%2) ans++;
          if((n/i)%2) ans++;
        } 
    }
    return ans;
}

정답코드 나눗셈 연산

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;
    while(n) n%2 && ans++, n/=2;
    return ans;
}