문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

N	A	B	answer
8	4	7	3

입출력 예 설명

입출력 예 #1
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

접근 방법

처음에는 N의 범위가 너무 커서 어떻게 접근해야 할지 고민을 많이 했다. 그러다가 입출력 예를 도식화 해보았고 여기서 중요한 패턴을 찾을 수 있었다.

A를 빨간색으로 표시하였고 B를 파란색으로 표시하였다. 도식화를 통해 알게 된 패턴은 각 참가자가 이기고 다음 단계로 올라갈 때에 자신의 번호가 절반이 된다는 사실이었다. 1단계에서 7번 참가자와 8번 참가자는 서로 번호가 바뀌어도 무방하다. B가 8번으로 바뀌게 되면 다음 단계에서 4번이 되기 때문에 내가 찾은 패턴에 만족한다.

이 패턴을 정리하면 만약 선택된 참가자가 홀수일 경우 1을 더해주고, (짝수일 경우에는 바로 진행) 2로 나눠준다. 이 과정을 A와 B가 같아질 때까지 진행하면 몇 단계에서 마주치는지 구할 수 있다.

• 정답을 저장할 변수 answer에 0을 저장한다.
• a와 b가 다를 동안 반복하는 while문을 돌린다.
  -> 만약 a%2가 1이라면 (a가 홀수인 경우) a에 1을 더한다.
  -> 만약 b%2가 1이라면 (b가 홀수인 경우) b에 1을 더한다.
  -> a와 b를 2로 나눈값으로 갱신한다.
  -> answer를 1 증가시킨다. (단계가 올라감을 구현)
• answer를 반환한다.

solution.py

def solution(n,a,b):
    answer = 0
    while a!=b:
        if a%2==1:
            a+=1
        if b%2==1:
            b+=1
        a, b=a//2, b//2
        answer+=1
    return answer