[Python] 예상 대진표

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 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

 

문제 풀이 순서

사실 나는 이걸 보고 토너먼트인 것을 알겠는데 이게 뭐 어떻게 풀라는 건가 싶었다. 막 리스트를 이용해서 2번째 배열을 만들어주고, 3번째 배열을 만들어줘서 거기에 우리가 찾고자 하는 A와 B가 최종적으로 들어있으면 되는 건가?라고 생각했다. 그렇게 하니 10초 이상이라는 시간 error가 떴고, 나의 친구 chatGPT에게 물어보았다... 돌아오는 답변은 코드 3줄이 다였다... 한심하지만 천천히 이해해보자

내가 만약 ①에서 1번째로 했어. 다음 라운드 때 이기면 나는 무조건 1번을 받겠네

내가 만약 ①에서 2번째로 했어. 다음 라운드 때 이기면 나는 무조건 1번을 받겠네

 

내가 만약 ①에서 3번째로 했어. 다음 라운드 때 이기면 나는 무조건 2번을 받겠네

내가 만약 ①에서 4번째로 했어. 다음 라운드 때 이기면 나는 무조건 2번을 받겠네

 

내가 만약 ①에서 5번째로 했어. 다음 라운드 때 이기면 나는 무조건 3번을 받겠네

내가 만약 ①에서 6번째로 했어. 다음 라운드 때 이기면 나는 무조건 3번을 받겠네

 

...

 

아하! n = (n+1) // 2 을 함으로써 결국에 목표한 값이 같을 때 while문을 나와서 return count하면 되겠구나!

def solution(n,a,b):
    count = 0
    while(a != b):
        a = (a+1) // 2
        b = (b+1) // 2
        count += 1

    return count