[PS] 점프와 순간

문제

해결

K칸 점프는 1칸 점프 K번과 도착 위치도 건전지도 같으니, 1칸 점프(건전지 1)와 순간이동(공짜)만 생각하면 된다. 그런데 순간이동은 지금까지 온 거리를 2배로 만들기 때문에, 같은 1칸이라도 뒤에 순간이동이 0번 남으면 1, 1번 남으면 2, 2번 남으면 4만큼의 거리가 된다. 4칸을 갈 때 4칸 점프는 건전지 4, 2칸 점프 후 순간이동은 2, 1칸 점프 후 순간이동 두 번은 1인 것도 이 때문이다.

그래서 이 문제는 사실 "1, 2, 4, 8… 카드를 골라 합이 n이 되게 할 때, 카드를 최소 몇 장 쓰는가"이다. 카드 한 장이 건전지 1이고, 어떤 카드 묶음이든 큰 카드부터 점프하고 순간이동하는 순서로 실제 경로를 만들 수 있다. 같은 카드는 여러 장 써도 되지만, 두 장을 빼고 한 단계 큰 카드 한 장을 넣으면 합은 그대로이고 카드는 1장 줄어든다. 예를 들어 6을 2 + 2 + 2(건전지 3)로 가는 대신 4 + 2(1칸 점프 → 순간이동 → 1칸 점프 → 순간이동, 건전지 2)로 갈 수 있다. 따라서 최소인 방법에는 같은 카드가 두 장 있을 수 없고, 같은 카드를 1장씩만 써서 n을 만드는 방법은 n의 2진수 하나뿐이다.

결국 답은 n을 2진수로 썼을 때 1의 개수다. n이 홀수면 1짜리 카드가 반드시 있으니 하나 세고 1을 빼고, 짝수면 1짜리가 없으니 절반으로 줄여 다음 자리를 보는 식으로 n이 0이 될 때까지 반복하면 된다.

코드

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