[programmers/py] 예상 대진표

예상 대진표

https://school.programmers.co.kr/learn/courses/30/lessons/12985?language=python3

문제 설명

게임 대회에 N명의 참가자 있습니다.
대회는 토너먼트 형식으로 참가하고 (1,2), (3,4) ... (n-1, n)번끼리 경쟁합니다.

(1,2) 그룹의 승자는 N/2번 즉, 1번을 부여받고
(3,4) 그룹의 승자는 2번을 부여받아 다음 라운드에 붙습니다.

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

제한사항

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

풀이

1. 결승에서 만나는 경우와 아닌 경우로 구분
   1-1. N이 8일 때 (1~4)번과 (5~8)번의 사람은 무조건 결승에서 만남
2. 승자는 항상 Math.ceil(n/2)의 번호를 다음 라운드에 부여
   1번 = 0.5->1, 2번 = 1->1, 3번 = 1.5->2, 4번 = 2->2
   두 사람이 같은 번호를 받으면 대결

import math
def solution(n,a,b):
    answer = 0
        
    mid = n // 2
    if (mid >= a and mid >= b) or (mid < a and mid < b):
        while a != b:
            a = (a+1) // 2
            b = (b+1) // 2
            answer += 1
    else : # 결승에서 만남
        answer = len(bin(n)[2:]) - 1

    return answer