[Python - Lv.2] 예상 대진표

문제

프로그래머스

문제

문제 이해

• 대회에 N명이 참가하여 토너먼트 형식으로 진행
• 참가자들은 1 ~ N번을 차례대로 배정받고 1-2, 3-4, (N-1)-N끼리 게임 진행
• 다음 라운드에서 참가자들은 1 ~ N/2번을 차례대로 배정받음(1-2의 게임에서 이기면 1번)
• 처음 라운드에서 A번인 참가자와 B번인 참가자는 몇 라운드에서 만나는가?
• N은 2의 지수이므로 부전승은 없고, A,B <= N (단, A != B)
• N, A, B는 입력으로 들어옴

풀이

1 2 3 4 5 6 7 8 ... N-1 N의 참가자가 있다고 해보자.
1-2의 게임에서 이기면 1, 3-4의 게임에서 이기면 2와 같이 다음 라운드에 번호가 배정된다.
이를 수식으로 표현하면, 승리했을 때의 다음 라운드의 번호는 (참가자 번호) / 2를 올림하여 구할 수 있다.
또한 (참가자 번호) / 2를 올림한 수가 같으면 A, B번의 참가자가 게임을 한다고 볼 수 있다.

1. math.ceil(A / 2), math.ceil(B / 2)를 통해 승리를 가정하고 다음 라운드의 번호 탐색
2. 1에서 구한 두 수가 같은지 확인, 다르면 round 1 증가 / 같으면 round 반환
3. 1 ~ 2를 반복

코드

import math

def solution(n,a,b):
    for round in range(1, n // 2 + 1):
        a, b = math.ceil(a / 2), math.ceil(b / 2)
        if a == b:
            return round