문제 제목은 기민한 사슴 정도 되겠군요.

BFS 문제 아닌가… 하다가 bitwise로 해결한 문제. 입력 범위가 아니라면 평범하게 풀었겠지만 \(10^{100}\)이라는 괴랄한 제한을 보고 규칙을 찾아야 했습니다.

재빠른 사슴이 잔디밭을 향해 뛰어갑니다. 이동 방식은 둘 중 하나입니다.

  • 앞 또는 뒤로 뛰기. 현재 속도가 \(i\)일 때 \(i\) 만큼 이동하고 속도가 \(2i\)가 됩니다.
  • 제자리뛰기. 위치는 변하지 않고 속도가 절반으로 줄어듭니다.

시작 속도는 \(1\)이고, \(n\) 위치로 가려고 할 때, 최소 이동 횟수를 구하면 됩니다.

일단 생각해볼 수 있는 건 BFS입니다. 현재 위치 \(x\) 및 현재 속도 \(i\)에 대해 \((x-i, 2i),(x+i, 2i),(x, i/2)\) 3개의 점에 간선이 연결되어 있으므로 전체 테스트케이스 40%에 대해 답을 구할 수 있습니다.

실제 최소 이동 횟수를 구해보면 \(n\)이 이진수일 때의 길이와 밀접한 관련이 있음을 알 수 있습니다.

규칙의 증명

\(2^N-1\) 꼴에 대해

비트가 111…로 표현될 경우, 계속 한 방향으로만 점프한 후 목표 지점에서 속도가 0일 될 때까지 제자리뛰기를 하면 됩니다. 이 경우 최소가 됩니다. 같은 거리를 다른 방식으로 가기 위해서는 더 긴 거리를 점프한 후 돌아가거나 어떤 거리를 두 번에 걸쳐 뛰어야 하는데, 횟수를 줄이면서 다른 방법으로 갈 수는 없습니다. 이 경우 이동 횟수는 \(2N+1\)입니다.

모든 홀수에 대해

잠깐 논의를 벗어나 사고실험을 해봅시다.

\(1, 2, 4, 8, … , 2^N\) 단위의 추를 양팔저울에 적절히 나눠 올릴 때 측정 가능한 무게는 몇 가지일까요.

조금 더 간단하게 바꿔서 \(N\)개의 추를 적당히 골라 만들 수 있는 무게를 생각해봅시다. 각 추의 단위는 2의 거듭제곱으로 이루어져 있으므로, 어떤 추를 고른다는 것은 이진법으로 표현 가능한 수에서 비트를 1로 만드는 것과 같습니다. 결국 만들 수 있는 무게는 \(0\)부터 \(2^{N+1}-1\)까지의 모든 수입니다. 임의의 추를 골라 만든 무게 \(x\)를 반대쪽 저울에 올리면 \(2^{N+1}-2x-1\)가 됩니다. 주어진 개수의 비트로 표현 가능한 모든 홀수를 만들 수 있습니다.

다시 사슴의 이야기로 돌아오겠습니다. 목표지점을 향해 점프하는 것은 추를 오른쪽 저울에 올리는 것으로, 목표지점의 반대쪽으로 점프하는 것은 추를 왼쪽에 올리는 것으로 생각할 수 있습니다. 저울의 예를 잘 생각해보면, \(1, 2, 4, 8…\) 순으로 뛰는 방향을 적당히 고르면 임의의 홀수 위치를 모두 갈 수 있다는 걸 알 수 있습니다. 이 때 최소 횟수는 모든 점프를 목표지점을 향해 할 때-\(2N+1\)-와 다르지 않습니다.

모든 짝수에 대해

처음 위치에서 1만큼 오른쪽으로 간 후 제자리뛰기를 한 번 하겠습니다. 그럼 이동해야 하는 거리는 \(n-1\)로 홀수가 되고 다시 위 방식으로 적당히 최소 횟수가 되도록 뛸 수 있습니다. 이 때 점프 횟수는 \(2N+3\)입니다. 다른 방법으로 가고자 한다면 최소 횟수로 이동하던 중 어떤 속도 \(i\)일 때를 몇 번에 걸쳐 나눠 가야하므로 상황이 더 나아지지 않습니다.

구현은 굉장히 단순해집니다. 그냥 짝수 여부와 이진수로 표현했을 때의 길이만 알면 됩니다.