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

1. k비용으로 k만큼 이동 (k > 0)
2. 0비용으로 현재 이동한 거리의 두 배만큼 이동

위의 두 동작을 적절히 이용하여 최소 비용으로 n에 도착하는 문제

처음에는 bfs로 접근했었는데 N의 최대가 $10^9$인 탓에 TLE가 나와버렸다. 한참 헤맸었는데 해법은 의외로 정말 간단했다. n부터 시작하여 0이 될 때까지 짝수일때는 나눗셈, 홀수일때는 뺄셈+비용증가를 시키면 되었다.

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

cpp code

#include <queue>
#include <set>

using namespace std;

using pii = pair<int, int>;

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