예상 대진표 ★★

통상적인 풀이 

def solution(n,a,b):
    # 발생할 수 있는 최대 라운드 수 계산
    max_round = 0
    while 2 ** max_round < n:
        max_round += 1
    
    # 이진 탐색 적용
    a, b = min(a, b), max(a, b)  # 큰 수, 작은 수 구분
    mid = n // 2  # 최초 중간값
    lower = 0  # 최초 최소값
    upper = n  # 최초 최대값
    
    while True:
        # 탈출 조건 // 두 수가 포함된 라운드가 서로 다를 경우
        if a <= mid and b > mid:
            break
        # 작은 수가 중간값보다 크거나 같을 경우(라운드에서 두 수가 같은 그룹에 있을 경우)
        elif a >= mid:
            lower = mid
            mid = (mid + upper) // 2
            max_round -= 1  # 라운드값 -1
        # 큰 수가 중간값보다 작거나 같을 경우(라운드에서 두 수가 같은 그룹에 있을 경우)
        elif b <= mid:
            upper = mid
            mid = (mid + lower) // 2
            max_round -= 1  # 라운드값 -1
            
    return max_round

코드 설명
▶이진탐색을 적용 

▶발생할 수 있는 최대 라운드의 수를 계산하기 위하여 while Loop을 활용, 

    2의 x제곱이 n과 같아지는 시점까지 max_round 변수를 1씩 증가시킴.

 

▶이진탐색을 적용하기 위하여 주어진 변수 a와 b의 대소를 비교하여 작은 수를 a에, 큰 수를 b에 재할당하고, 

   최초 중간값/최소값/최대값을 설정

▶while Loop을 무한 반복하되, 탈출조건으로 두 수가 서로 다른 라운드에 포함되어있을 경우를 설정

 

▶이후 라운드에서 두 수가 같은 그룹에 있을 경우를 두 경우로 

   분할(작은 수가 mid 보다 클 경우, 또는 큰 수가 mid보다 작을 경우)하여

    해당 경우에는 max_round를 1씩 뺀다.

 

▶ 정정: 작은 수a 가 중간값(mid)과 같거나 중간값(mid)보다 큰 경우

 

 

 

 

진화된 풀이 

def solution(N, A, B):
    # A번 참가자가 B번 참가자와 만날 때까지 거쳐야 하는 라운드 수
    round = 0
    # A번 참가자가 B번 참가자와 다를 때까지 계속 반복
    while A != B:
        # A번 참가자와 대결할 상대를 구함
        A = (A + 1) // 2
        B = (B + 1) // 2
        # 라운드 수 1 증가
        round += 1
    # 라운드 수 반환
    return round

▶ 아래에서 올라갈 때 새로 부여받는 번호의 규칙성을 이용한다. 

 

▶ 번호의 규칙성 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

 

▶ 1 ~ 8의 번호가 있을 때, 단순히 2로 나눈 몫은 0 1 1 2 2 3 3 4 이지만 1을 더했을 경우 1 1 2 2 3 3 4 4가 된다.

 

▶ 위와 같은 경우 두 번호가 같아 질때 "맞다이"를 한다.