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

 이 문제는 프로그래머스 level 2에 있는 문제이다. 이 문제를 풀기 위해 많은 노력을 기울였지만 풀지 못했다. 정답 횟수를 1부터 n / 2까지 돌리면서 해당 숫자로 n까지 갈 수 있는지로 풀어봤지만 이건 시간 초과가 발생하고 애초에 정답도 안 나온다. 다른 어떤 방법을 써도 완전 탐색과 같은 방향으로 시간 초과가 나지 않을 수는 없었다.

 

 그래서 구글링을 통해 코드를 봤는데, n부터 시작해서 2로 나눈 나머지를 보고 1이면 점프 횟수를 추가하는 방식으로 하면 무조건 정답이 나올 것이라는 생각이 들었다. 그리디한 방식이었는데, 이렇게 간단한 방법을 생각하지 못해 아쉬웠다.

 

#include <iostream>

using namespace std;

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