[백준] 22973 점프 숨바꼭질 (파이썬)

https://www.acmicpc.net/problem/22973

22973번: 점프 숨바꼭질

링크(https://www.acmicpc.net/category/detail/2751) 하단의 풀이 슬라이드를 참고했는데 풀이를 보고도 이해하는 데에 시간이 오래 걸렸다.

 

방법 1.

K = abs(int(input()))
if K == 0:
    print(0)
elif K % 2 == 0:
    print(-1)
else:
    ans = 0
    while K > 0:
        K = K >> 1
        ans += 1
    print(ans)

점프 횟수 = 3이라고 예시를 고정하자. 뛸 수 있는 점프는 1, 2, 4이고 +, - 둘 다 된다.

이런 류의 문제는 bfs로 깊이(=거리)를 찾아내는 게 일반적인데 이 문제는 아니다. 모든 지점에 도달 가능하다면 bfs로도 될 것 같긴 하나, 현재 깊이에서 아직 지점에 도달하지 못했다면 미래에 될지 안 될지 가지치기 여부를 파악하기 힘들다. 애초에 도달 여부와 도달 깊이를 알기 위해 지금 이 문제를 쓰는 건데 일종의 순환논증 혹은 선결문제인 셈이다.

일단 점프의 길이를 적어보자. 1, 2, 4, ~~~ 이다. 모두 +로 뛴다고 하자. 0번째 점프(점프를 뛰지 않는다면)는 거리가 0, 짝수이다. 1번째 점프는 거리가 1, 홀수이다. 2번째 점프는 거리가 2, 짝수이다. 3번째 점프는 거리가 4, 짝수이다. 홀수+짝수=홀수라는 점을 생각하자. 즉 0번째 점프라면 거리 0에 도달하고, 0이 아닌 양의 정수 번째 점프라면 거리 홀수에 도달한다. 거리가 짝수인 지점에 도착하는 점프 횟수는 없다. 아래의 코드를 만들 수 있다.

if K == 0:
    print(0)
elif K % 2 == 0:
    print(-1)

점프 방향, 거리 방향은 0을 기준으로 대칭이니 일반성을 잃지 않고 절댓값을 K에 씌워주자. 2배씩 증가한다는 점이 2진수 혹은 비트를 생각나게 하니 비트로 K를 적어보자.

여전히 점프 횟수 = 3이고 모두 +로 뛴다고 생각해보자.
111(=7)
이다.
이때 1짜리 점프를 무르고 마이너스 방향으로 뛴다고 생각해보자. 즉 비트(111) - 2*비트(001)을 해보자.
101(=5)
이 된다. 1짜리 점프는 1=2^0이기 때문에 0번째 비트 자리이고 이 점프를 마이너스로 뛰었더니 한 칸 왼쪽 비트가 0으로 변한다.
마찬가지로 2짜리 점프를 무르고 마이너스 방향으로 뛴다고 생각해보자. 비트(111) - 2*비트(010)을 해보자.
011(=3)
이 된다. 이번에도 한 칸 왼쪽 비트가 0으로 변한다.

즉 모두 +로 뛴다고 가정을 한 후 i번째 점프를 뒤로 뛴다면, i+1번째 비트가 0으로 변하는 것이다.

이때 4짜리 점프를 무르고 뒤로 뛴다고 해보자. 비트(111) -  2*비트(100)일 것이다. 이때 4짜리 점프를 뒤로 뛰면 언제나 K는 음수라는 점을 떠올려보자. An이 수열, Sn이 수열의 합의 수열이라 치면 An = Sn-1+1이기 때문에 언제나 음수이다.
음수 비트의 계산은 복잡하니 우회를 하자. 우리는 이미 일반성을 잃지 않고 절댓값을 씌워줬다. (4짜리 점프를 뒤로 & 나머지 점프를 무언가로) = -(4짜리 점프를 앞으로 & 나머지 점프를 -무언가로)이니 abs(4뒤&나머지 무언가) = abs(4앞&나머지 -무언가)일 것이다. 이제 '4앞&나머지 -무언가'만 생각하면 된다. 마지막 비트가 아닌 비트가 마이너스로 뛰는 것은 이미 알고 있다. 4가 +, 나머지 모두가 -라면
001(=1 혹은 -1)
가 된다.

 

0번째 비트는 1로 고정이지만, 다른 비트는 0과 1 모두 가능하다. 즉 어떤 수열에 따라 n번 점프를 뛰는 것은 n비트로 표현할 수 있는 모든 숫자(단 0비트=1)이다. n비트는 2^n-1 이하의 모든 정수를 표현할 수 있으니 2^n-1 이하의 모든 홀수이다. n번 점프를 뛰는 것은 n비트로 표현할 수 있는 모든 홀수 지점에 도착할 수 있다.

수 5는 비트 101(비트111에서 0번째 비트가 마이너스 = 7-2)로도 표현할 수 있고 비트 0101(비트1111에서 0번째, 2번째 비트가 마이너스=15-8-2)로도 표현할 수 있으나 최소 점프 횟수니 전자를 택한다.

이하는 비트의 길이를 재는 방식이다.

    ans = 0
    while K > 0:
        K = K >> 1
        ans += 1
    print(ans)

 

방법 2.

K = int(input())
if K == 0:
    print(0)
elif K % 2 == 0:
    print(-1)
else:
    print(K.bit_length())

K=0일 때, K=짝수일 때는 위와 동일하니 생략한다.

접근 방식을 바꿔보자. K=3이고 모든 점프를 +로 뛴다면 2^n-1 = 2^3-1=7 지점에 도착한다. 이때 어떤 점프를 무르고 마이너스로 뛴다고 생각해보자. (i는 0부터 시작)i번째 점프의 거리 = 2^i이다. 우리가 도착할 수 있는 최종 지점은 다음과 같다.

(단 i = 0 이상 n 미만의 정수 혹은 정수들)
그런데 이때 우항의 summation 텀은 n비트로 표현될 수 있는 0 또는 양의 정수와 같다. n비트는 2^n-1을 모두 표현할 수 있다. 해당 수식은 결국 -( 2^n-1 ) 이상 ( 2^n-1 ) 이하인데 곱하기 2를 했으니 1칸씩 건너 뛴다. 홀수에서 시작해서 1칸씩 건너 뛰었으니 해당 숫자들은 모두 홀수다.

즉 n번 점프를 뛴다는 것은 -(n비트로 표현할 수 있는 모든 홀수) 이상  (n비트로 표현할 수 있는 모든 홀수)이하의 정수에 도착한다는 뜻이다. n+1번 점프를 뛰어서도 도착할 수 있겠으나 최소 횟수를 구해야 하니 전자를 택한다. K를 (n비트로 표현된 정수)로 바꾸고 이것의 길이를 측정하면 n이 나온다.

else:
    print(K.bit_length())