Programmers - 점프와 순간 이동

---

title: Programmers - 점프와 순간 이동
date: 2022-07-11
tags:

• Algorithm

---

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

문제 요약

0을 시작으로 n까지 움직여야 한다. 배터리 1당 1을 움직일 수 있으며, 혹은 배터리 소모 없이 지금까지 온 거리만큼 순간이동 할 수 있다.
n까지 이동할 때 사용할 최소 배터리 사용량을 return한다.

문제 풀이

최대 1B까지 움직여야 하는 문제이다. 크기를 먼저 보았을 때, DP일 것이라 예측하였다.
하지만 문제를 읽고나니 DP 방식으로 접근하도록 유도하는 거짓 문제임을 알 수 있었다.
처음에 1을 이동할 때는 배터리를 무조건 1을 사용한다. 그 이후로는 순간이동을 하면 약 530M까지는 배터리 소모 1로 이동할 수 있다.
이는 결국 순간이동을 최대한 활용하는 문제이고, 결국 비트 연산 문제임을 알 수 있다.

0에서 시작을 하면 무수히 많은 중간 과정을 고려해야 하지만, 거꾸로 생각하면 매우 쉽다. n에서 0까지 이동한다고 생각하면 된다.
n에서 이동할 때는 오히려 반씩 접으면 되며, 홀수일 경우 배터리를 1 소모하는 것이다.
결국 이 문제는 비트 표현시, 1의 개수를 세는 문제인 것이다.
n & 1 연산을 통해 1 비트를 확인하고, shift 연산을 반복해주면 된다.

프로그램

#include <vector>

using std :: vector ;

int solution ( int n )
{
    int iReturn = 0 ;



    while ( 1 < n )
    {
        if ( 1 == ( n & 1 ) )
            ++ iReturn ;

        n >>= 1 ;
    }

    return iReturn + 1 ;
}