[C++] (DP) 점프와 순간이동

 

점프와 순간이동

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요. 

 

 

제한 사항 숫자 N: 1 이상 10억 이하의 자연수 숫자 K: 1 이상의 자연수

 

 

 

입출력 예

5	2
6	2
5000	5

 

 

 

 

처음에 10억개 이상 배열을 만드는 DP를 생각했다가 다시 접근했습니다.

 

 

최대한 베터리를 안쓰고 2배로 뛰어서 많이 가야합니다. 0부터 출발이 아닌 n부터 거꾸로 도착하는 경우를 생각하면 됩니다.

 

예를들어 n이 6이라 하면, 3에서 점프를 해야합니다. 점프를하면 6칸까지 갈때 3칸에서 두배를 점프하여 3칸까지 이동하는 베터리사용량과 동일하게 됩니다. 

 

6 -> 3 -> 2 -> 1 -> 0

 

5000 -> 2500 -> 1250 -> 625 ->  624(1) -> 312 -> 156 -> 78 -> 39 -> 38(2) -> ....  ( 625부터 5000까지 베터리사용량은 0 )

 

 

즉, 짝수번째 칸까지 도달하려면 그 칸의 절반의 칸에서 점프하면 됩니다. 이때, 점프하는 칸이 홀수일 경우,아래에서 홀수칸까지 경우를 생각해봅니다. 예를들어, 3칸까지 오는 경우를 생각하면 2에서 1칸 더 오는 경우가 가장 최소의 베터리 사용이 됩니다.

쉽게말하면, 짝수는 현재 위치 칸의 두 배 만큼 점프하면 소모베터리가 0이므로, 점프 했을때 도착지칸이 두배가 되는 2/마지막자리가 되고, 홀수는 n X 2일때 홀수가 되는 n값은 없기때문에 무조건 마지막 두배 후 한칸 이동해줘야합니다.

 

 

 

따라서, 베터리 사용량은 n이 짝수이면 자신의 절반까지 오는데 사용한 베터리, 홀수이면 ((자신 - 1)의 절반까지 온값) + 1이 됩니다.

n이 0이 될때까지, 2로 나누면서 짝수와 홀수가 되는경우를 나눠서 반복합니다. 

 

 

 

풀이

#include <iostream>

using namespace std;

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