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

프로그래머스의 점프와 순간이동(Lv2) 문제이다.

 

[ 문제풀이 ]

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

 

간단한 예시를 하나 들어서 문제에 접근해보자.

N = 100 일 때의 결과값을 도출하는 과정을 진행해보자.

과연, 어떻게 움직여야 건전지를 최대한 덜 사용하고 100번째 칸 까지 갈 수 있을까 ??

갈 수 있는 방법에는 2가지 방법이 있다.

1. 순간이동을 통해, 사용량 0을 사용해서 지금까지 온 거리 x 2 를 통해서 움직이는 방법

2. K 칸을 점프해서, 건전지를 K만큼 사용해서 움직이는 방법

 

그럼, 최대한 많은 순간이동을 사용하는 방법이 건전지의 사용량을 최소화 시킬 수 있을 것이다.

왜냐하면, 순간이동에는 건전지 사용량이 줄어들지 않기 때문이다.

그렇다면 100번째 칸 까지 가기 위해서 크게 본다면 이렇게 접근해 볼 수 있다.

50번째 칸 까지 간 후에, 순간이동 해버리기 !

그렇게 된다면 50번째 칸 까지만 간 후에 건전지 사용량 0으로 100번째 칸 까지 갈 수 있을 것이다.

그럼, 50번째 칸 까지는 어떻게 갈 수 있을까 ?

마찬가지이다. 25번째 칸 까지 간 후에 건전지 사용량 0으로 50번째 칸 까지 순간이동 해버리기.

그럼, 25번째 칸 까지는 어떻게 갈 수 있을까 ?

순간이동으로 갈 수가 없는 칸이다. 왜 그럴까 ?? 순간이동은 "지금까지 온 거리 x2" 만큼을 순간이동을 할 수 있는 것이다. 그렇다면, 순간이동으로 25번째 칸 까지 가기 위해서는 지금까지 온 거리가 12.5 칸 이여야 한다는 이야기인데, 이 문제에서 K는 자연수 이기 때문에 12.5칸을 움직일 수는 없다.

그렇기 때문에 이 경우에는 건전지를 K만큼 사용해서 움직이는 방법을 사용해야 한다.

바로, 24번째 칸 까지 온 후에 1만큼 사용해서 25번째 칸으로 왔다고 가정을 하는 것이다.

그렇게 되면 ? 24번칸 까지는 ? 12번칸 까지 간 후에 순간이동을 해버리면 되는 것이다.

12번 칸 까지는 ? 6번칸까지 간 후에 순간이동. 6번칸 까지는 ? 3번칸 까지 간 후에 순간이동.

3번칸 까지는 ? 1.5칸을 간 후에 순간이동을 해야 하는데 갈 수 없으므로, 2번 칸에서 1만큼 건전지를 사용해서 3으로 가게 만들어 주는 것이다.

 

즉 ! 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
        {
            n -= 1;
            ans++;
        }
    }
    return ans;
}