[브루트포스/수학] 백준 1057 토너먼트 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1057번: 토너먼트

 

 

 

2. 문제 풀이

 계속 이긴다는 보장 하에, 두 사람이 매칭되는 라운드를 구하는 문제입니다.

 

 

 예를 들어, 2번과 4번은 2라운드에서 만나게 됩니다. 브루트포스 방식으로 완전탐색해서 풀려면, 위와 같이 완전 이진트리를 구성하고 일일이 탐색하면 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, a, b = map(int, input().split())

# 토너먼트
cnt = 0
while a != b:
    a -= a // 2
    b -= b // 2
    cnt += 1
print(cnt)

 저는 토너먼트의 규칙을 이용해서 수학적으로 접근했습니다. 문제에서 번호 매기는 순서는 '처음 번호의 순서를 유지하면서 1번부터 매긴다'라고 합니다.

 3번과 4번이 스타를 해서 4번이 진출했다면, 4 - 4/2 = 2번을 부여받게 됩니다. 한편 3번이 진출했어도 3 - 3//2 = 2번으로 같습니다. 즉, 이겼을 때 다음 라운드에서의 번호는 'N - N//2'로 계산할 수 있습니다.

 지민이와 한수가 매칭되었다면, 둘의 다음 라운드에서의 번호는 같습니다. 따라서, 둘의 다음 라운드에서의 번호가 같을 때까지 탐색해서 라운드 수를 구합니다.