[C++로 풀이] 점프와 순간 이동⭐⭐

📌 점프와 순간 이동

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

using namespace std;

int solution(int n)
{
    int ans = 0;
    
    while(n > 0){
        if (n % 2 == 1)
            ans++;
        n /= 2;
    }

    return ans;
}

2로 계속 나눴을 때 나머지가 1 이 되는 것이 몇 개 인지를 세면 그게 답이다! 즉, n을 이진수로 변환했을 때 1의 개수를 세면 된다. 그 이유는 아래와 같다.

• 출발할 때 점프하는 것은 불가피하다. 순간이동은 현재까지 온 거리에서 X 2 를 할 수 있기 때문.
• 순간이동은 현재까지 온 거리의 2 배를 갈 수 있고, 건전지를 소모하지 않기 때문에 최대한 많이 사용해야 한다.
• 순간이동 했을 때 딱 맞아 떨어지지 않는, 즉 곱하기 2 를 했을 때 딱 맞아 떨어지지 않는 경우에만 + 1 을 해주면 된다.
  • 즉 이럴때만 점프하여 건전지를 소모하면 된다.

5000의 경우 최소 건전지 소모량은 5 인데 위와 같은 원리!

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기