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

문제 URL

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

프로그래머스

위 문제는 n칸까지 가야 할 때, 건전지 사용량을 최소화 시켜서 도달하는 문제이다.

정해진 n칸까지 가는 경우의 수는 여러가지가 있는데 그중 건전지 사용량을 최소로 하는 경우는 순간이동을 하는 수를 늘리는 방법이다. 

 

만약 n이 100이라고 했을 때 50까지 도달했다면 그 뒤는 순간이동할 수 있다. 

그렇다면 50에 도달하려면 25까지 오면 순간이동으로 50에 도달할 수 있다.

같은 방식으로 25에 도달하려면 12.5까지 오면 순간이동으로 도달할 수 있는데 이때 12.5는 자연수가 아니므로 12까지 도달한 다음 +1을 해주는 방식으로 생각을 해준다. 

12에 도달하려면 6, 6에 도달하려면 3, 3에 도달하려면 1에 도달한 뒤 +1

다음과 같은 방식에 따르면 결국 건전지 사용량은 3이 된다. (처음 0일 때 1로 도약하는 상황 포함)

 

위 방식에 따라 코드를 작성하면 n이 0이 될 때까지 while문을 도는데 n이 짝수라면 건전지가 필요없이 순간이동할 수 있으므로 건전지 사용량의 개수를 추가시키지 않고 새로운 n(=n/2)을 만들고, 만약 n이 홀수라면 +1의 도약이 필요하므로 건전지 사용량의 개수에 +1을 추가하며 새로운 n(=n-1)을 만든다. 

---

#include <iostream>
using namespace std;
 
int solution(int n)
{
    int ans = 0;  // 건전지 사용량 
    while(n != 0) {
        if(n % 2 == 0) 
            n /= 2;
        else
        {
            n -= 1;
            ans++;
        }
    }
    return ans;
}