문제 요약
N명의 참가자가 토너먼트를 진행합니다.
- 1번과 2번
- 3번과 4번
- 5번과 6번
- ...
위와 같이 인접한 번호끼리 경기하며, 승자는 다음 라운드에 진출합니다.
다음 라운드에 진출한 참가자들은 경기 순서에 따라 다시 1번부터 번호를 부여받습니다.
처음 번호가 A, B인 두 참가자가 서로 만나기 전까지 항상 승리한다고 할 때, 두 참가자가 몇 번째 라운드에서 만나는지 구해야 합니다.
핵심 아이디어
현재 라운드에서 참가자 번호가 x라면 다음 라운드에서 받는 번호는 다음과 같습니다.
(x + 1) // 2예를 들어 번호가 1부터 8까지라면 다음 라운드 번호는 아래와 같이 바뀝니다.
| 현재 번호 | 다음 라운드 번호 |
|---|---|
| 1, 2 | 1 |
| 3, 4 | 2 |
| 5, 6 | 3 |
| 7, 8 | 4 |
홀수 번호와 바로 다음 짝수 번호가 하나의 경기 조를 이루므로 두 번호 모두 같은 값으로 변환됩니다.
따라서 A와 B에 이 계산을 반복해서 적용하고, 두 번호가 처음 같아지는 시점을 찾으면 됩니다.
두 번호가 같아지는 시점
예제의 A = 4, B = 7을 살펴보겠습니다.
| 라운드 | A의 번호 | B의 번호 |
|---|---|---|
| 시작 | 4 | 7 |
| 1라운드 종료 후 | 2 | 4 |
| 2라운드 종료 후 | 1 | 2 |
| 3라운드 종료 후 | 1 | 1 |
3라운드의 경기가 끝난 뒤 두 참가자의 번호가 처음으로 같아집니다.
이는 두 참가자가 3라운드에서 같은 경기에 배정되어 서로 만났다는 뜻입니다. 따라서 정답은 3입니다.
알고리즘
- 라운드 수를 저장할
answer를 0으로 초기화합니다. A와B가 서로 다른 동안 다음 과정을 반복합니다.- 두 번호를 각각
(번호 + 1) // 2로 변경합니다. answer를 1 증가시킵니다.- 두 번호가 같아지면
answer를 반환합니다.
Python 풀이
def solution(n, a, b):
answer = 0
while a != b:
a = (a + 1) // 2
b = (b + 1) // 2
answer += 1
return answern은 전체 대진표의 크기를 나타내지만, 두 참가자의 번호가 변하는 과정만 추적하면 되므로 계산에서 직접 사용할 필요는 없습니다.
실행 과정
n = 8
a = 4
b = 7각 반복이 끝난 뒤의 값은 다음과 같습니다.
초기 상태: a = 4, b = 7, answer = 0
1회 반복: a = 2, b = 4, answer = 1
2회 반복: a = 1, b = 2, answer = 2
3회 반복: a = 1, b = 1, answer = 3두 번호가 같아졌으므로 반복을 종료하고 3을 반환합니다.
복잡도 분석
참가자 수 N은 2의 거듭제곱이며, 라운드가 진행될 때마다 참가자 수가 절반으로 줄어듭니다.
- 시간 복잡도:
O(log N) - 공간 복잡도:
O(1)
두 참가자의 번호만 저장하여 계산하므로 별도의 대진표를 만들 필요가 없습니다.
정리
이 문제에서는 실제 토너먼트 대진표를 구현하지 않아도 됩니다. 각 참가자의 번호가 다음 라운드에서 어떻게 변하는지만 추적하면 됩니다.
핵심 변환식은 다음과 같습니다.
다음 번호 = (현재 번호 + 1) // 2두 참가자의 번호가 처음 같아지는 순간이 바로 두 참가자가 맞붙은 라운드입니다.
