Rączy jelonek
문제
(claude 번역)
민첩한 사슴이 긴 점프로 숲의 공터를 향해 이동합니다.
사슴은 에너지가 넘쳐서 매번 점프가 이전보다 최대 두 배까지 길어질 수 있습니다.
형식적으로 말하면, 매 순간 사슴의 에너지는 특정 레벨 i에 있습니다.
사슴은 두 가지 이동 방법이 있습니다.
수평 점프: i미터를 앞 또는 뒤로 점프하며, 자동으로 에너지 레벨이 2i로 전환됩니다.
수직 점프: 공터로 가는 길에서 이동하지 않고 제자리에서 점프하며, 에너지 레벨이 i/2로 전환됩니다.
처음에 사슴의 에너지는 1입니다. 에너지가 1일 때 수직 점프를 하면 사슴은 멈춥니다.
아래는 길 왼쪽에서 시작한 민첩한 사슴의 예시 여행입니다.
화살표 위의 숫자는 해당 점프 후 사슴의 에너지 레벨을 나타냅니다. 값 0은 사슴이 멈췄음을 의미합니다.
공터로 가는 길은 양방향으로 무한합니다.
즉, 사슴은 여행 중에 공터를 지나치거나 출발 지점보다 앞에 있을 수 있습니다.
사슴과 목표 지점 사이의 거리는 처음에 n미터입니다.
사슴이 공터에 도달하여 멈추는 데 필요한 최소 점프 횟수를 계산하세요.
입력
첫 번째 줄에 사슴과 공터 사이의 거리를 나타내는 정수 n (1 ≤ n ≤ 10^100)이 주어집니다.
출력
사슴이 공터에 도달하여 멈추는 데 필요한 최소 점프 횟수를 나타내는 정수 하나를 출력하세요.
풀이
우선 입력 값이 너무 커서 python으로 풀어야겠다고 생각했고, 이진수와 어떤 관계를 쓰는 것 같았다.
하지만 뭔가 방법이 생각나지도 않고, 태그를 까보니 BFS?라고 해서 더 모르게 되었다.
그래서 답을 찾다보니 koosaga님 github에서 푼 코드가 있어서 읽어봤는데 아이디어가 되게 재밌다.
우선 마지막 자리에 멈춰야 하기 때문에 도착한 후 에너지는 0이 되어야 한다.
그리고 수평으로 점프를 할 때는 에너지가 2배씩 늘어난다.
그러면 0이 되기 위해서 필요한 제자리 점프의 횟수는 수평 점프 수 + 1이 되어야만 한다.
그러고서 이제 수를 이진수로 표현할 방법을 생각하면 된다.
우선 n이 홀수일 때는 이진수로 변환한 후 자릿수만큼의 점프로 전부 표현이 가능하다.
예를 들어 93(0b1011101) 같은 경우에는 -1 + 2 + 4 + 8 - 16 + 32 + 64가 된다.
그러므로 총 7*2+1 = 15번이다.
n이 짝수일 때는 시작 에너지가 1이기에 앞에 거쳐야 하는 과정이 있다.
-1,제자리, 1로 왔다갔다하면 0에서부터 시작 에너지를 2로 가진채 움직일 수 있다.
이 때 홀수에 비해 +2번만큼의 움직임이 추가되고, 그 후 방법은 위와 동일하다.
문제를 풀고 풀이를 보니 이런저런 방법들이 있는 것 같은데 위의 아이디어가 되게 멋있다고 생각이 든다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
ans = 1
if n%2==0:
n-=1
ans+=2
while n>=1:
n//=2
ans+=2
print(ans)
#1011101
#-1 + 2 + 4 + 8 - 16 + 32 + 64
#110
#-1+1+2+4