C++에서 토너먼트 우승자가 치를 수 있는 최대 경기 수

문제 개요

N명의 플레이어가 참가하는 토너먼트가 열린다고 가정해 봅시다. 이때 구해야 할 것은 우승자가 치를 수 있는 경기 수의 최댓값입니다.

단, 이 토너먼트에는 특별한 규칙이 있습니다. 두 플레이어는 각자 지금까지 치른 경기 수의 차이가 1 이하일 때만 서로 대결할 수 있습니다. 이 제약 조건 때문에 단순히 모든 경우를 세는 방식으로는 문제를 풀기 어렵습니다.

예시

플레이어가 3명이라면, 다음과 같이 2번의 경기만으로 우승자를 결정할 수 있습니다.

• 경기 1: 플레이어 1 vs 플레이어 2
• 경기 2: 경기 1의 승자 vs 플레이어 3

이렇게 진행하면 우승자는 최대 2경기를 소화하게 되며, 이것이 3명의 플레이어로 만들 수 있는 최댓값입니다.

알고리즘 접근 방식

이 문제는 사고의 방향을 뒤집으면 훨씬 간단해집니다. 즉, "우승자가 x번의 경기를 치르려면 최소 몇 명의 플레이어가 필요한가?"를 먼저 계산하고, 원래 문제는 그 역문제로 해석하는 것입니다.

• dp[i]를 "우승자가 i경기를 치르기 위해 필요한 최소 플레이어 수"라고 정의합니다.
• 준우승자가 (i − 1)경기, 우승자가 i경기를 치렀다고 할 때, 두 사람이 그동안 맞대결했던 상대 선수 집합은 서로 겹치지 않습니다. 따라서 필요한 전체 플레이어 수는 두 집합의 합이 되며, 이를 점화식으로 표현하면 다음과 같습니다.
  dp[i + 1] = dp[i] + dp[i − 1]
• 이 점화식은 dp[i] = dp[i − 1] + dp[i − 2] 형태로 바꿔 쓸 수 있으며, 이는 바로 피보나치 수열의 관계와 동일합니다.

따라서 최종 답은 입력으로 주어진 플레이어 수 n보다 작거나 같은 가장 큰 피보나치 수의 인덱스가 됩니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

int getMaxGamesToDecideWinner(int n) {
    int dp[n];
    dp[0] = 1;   // 우승자가 1경기를 치르려면 최소 1명 필요
    dp[1] = 2;   // 우승자가 2경기를 치르려면 최소 2명 필요
    int idx = 2;
    do {
        dp[idx] = dp[idx - 1] + dp[idx - 2];
    } while (dp[idx++] <= n);
    return (idx - 2);
}

int main() {
    int players = 3;
    cout << "Maximum games required to decide winner = "
         << getMaxGamesToDecideWinner(players) << endl;
    return 0;
}

코드 설명

dp 배열에는 피보나치 수열이 순서대로 저장됩니다. 초기값으로 dp[0] = 1, dp[1] = 2를 설정한 뒤, do-while 반복문을 통해 값이 입력된 플레이어 수 n을 초과할 때까지 점화식대로 수를 생성합니다. 반복문이 종료되는 시점의 인덱스를 보정하면, n 이하인 가장 큰 피보나치 수의 위치, 곧 우승자가 치를 수 있는 최대 경기 수를 얻을 수 있습니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Maximum games required to decide winner = 2

복잡도 분석

피보나치 수는 기하급수적으로 빠르게 증가하기 때문에, n을 초과하는 첫 번째 피보나치 수에 도달하기까지 필요한 반복 횟수는 매우 적습니다. 따라서 시간 복잡도는 O(log n) 수준이며, dp 배열 사용으로 인한 공간 복잡도는 O(n)입니다.