문제 이해하기
숫자 n이 주어졌다고 가정해 봅시다. 토너먼트에는 n개의 팀이 참가하며, 다음과 같은 규칙이 적용됩니다.
현재 팀 수가 짝수라면, 각 팀은 다른 팀과 짝을 이루어 경기를 진행합니다. 총 (n/2)경기가 치러지고, 승리한 (n/2)개 팀이 다음 라운드로 진출합니다.
현재 팀 수가 홀수라면, 한 팀은 부전승으로 자동 진출하고 나머지 팀들은 서로 짝을 이룹니다. 따라서 총 (n-1)/2경기가 치러지며, (n-1)/2+1개 팀이 다음 라운드로 진출합니다.
우리의 목표는 최종 우승 팀이 가려질 때까지 치러진 총 경기 수를 구하는 것입니다.
예시
예를 들어 n = 10이라면 결과는 9가 됩니다. 그 과정은 다음과 같습니다.
처음에 10팀을 5-5로 나누어 경기를 진행하면, 5개 팀이 다음 라운드에 진출합니다.
한 팀이 부전승으로 통과하고 나머지 4팀을 2-2로 나누면, 3개 팀이 진출합니다.
다시 한 팀이 부전승으로 통과하고 나머지 2팀을 1-1로 나누면, 2개 팀이 진출합니다.
마지막으로 1-1 대결을 통해 최종 우승 팀이 결정됩니다.
풀이 접근 방법
이 문제는 매 라운드마다 치러진 경기 수를 누적하는 방식으로 해결할 수 있습니다. 알고리즘 단계는 다음과 같습니다.
정답 변수 ans를 0으로 초기화합니다.
n이 1이 아닌 동안 아래 과정을 반복합니다.
f ← n을 2로 나눈 몫 (n // 2)
remainder ← n을 2로 나눈 나머지 (n % 2)
ans ← ans + f
n ← f + remainder
반복이 끝나면 ans를 반환합니다.
Python 코드 예제
아래 구현을 통해 더 잘 이해할 수 있습니다.
def solve(n):
ans = 0
while n != 1:
f = n//2
remainder = n % 2
ans += f
n = f + remainder
return ans
n = 10
print(solve(n))입력
10
출력
9
추가 팁
사실 이 문제에는 흥미로운 수학적 사실이 숨어 있습니다. 경기가 한 번 치러질 때마다 정확히 한 팀이 탈락하므로, n개 팀에서 1개의 우승 팀을 남기려면 반드시 n-1개 팀이 탈락해야 합니다. 즉, 토너먼트 규칙과 무관하게 총 경기 수는 항상 n-1입니다. 위 코드도 이 원리와 일치하는 결과를 출력하며, 시간 복잡도는 O(log n)으로 매우 효율적입니다.