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

1. 문제

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

프로그래머스

 

2. 문제 풀이

이 문제는 점프와 순간 이동 중에 선택해서 에너지 사용량을 최소가 되도록 하여 최솟값을 반환해야 한다. 점프를 하면 한 번에 원하는 좌표로 이동할 수 있지만 에너지 사용량이 점프한 칸 수만큼 추가되어야 한다. 순간이동은 현재 좌표에서 2배에 해당하는 좌표로 이동할 수 있는데 에너지 사용량은 변화가 없다. 

 

처음에는 0에서 4, 0에서 3, 0에서 2, 0에서 1까지 점프한 다음, 순간이동이 가능한지 확인했다. (현재 좌표) * 2 == N(목표 지점), (현재 좌표) * 2 < N, (현재 좌표) * 2 > N으로 나누었다. 그래서 (현재 좌표) * 2이면 break하여 min 값을 비교하고, (현재 좌표) * 2 < N이면 이 과정을 반복하는 것으로 생각했다. 그러나 너무 따질 게 많고 복잡해서 다시 한 번 생각했다.

 

일단, 순간이동을 할 수 있으려면, 당연히 (현재 좌표) * 2 가 목표 지점인 N보다 작아야 한다. 반대로 생각해서 N을 2로 나누었을 때 홀수이면 순간이동을 할 수 없기 때문에 에너지 사용량을 늘리고 현재 위치 N에 1을 뺀다. 2로 나누었을 때 짝수이면 순간이동이 가능하기 때문에 N을 2로 나누어 준다.

 

3. 코드

#include <iostream>
using namespace std;

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

    return ans;
}