C++에서 승자가 플레이한 최대 게임 수

문제 설명

토너먼트를 하는 N명의 플레이어가 있습니다. 승자가 할 수 있는 최대 게임 수를 찾아야 합니다. 이 토너먼트에서는 두 명의 플레이어가 플레이한 게임 간의 차이가 1개 이하인 경우에만 서로 대결할 수 있습니다.

예시

3명의 플레이어가 있는 경우 다음과 같이 승자를 결정하기 위해 2개의 게임이 필요합니다 -

게임 – 1:플레이어 1 대 플레이어 2

게임 - 2:플레이어 2 대 게임 - 1의 승자

알고리즘

• 우선 승자가 x 게임을 플레이하는 데 필요한 최소 플레이어 수를 계산하여 이 문제를 해결할 수 있습니다. 이것이 계산되면 실제 문제는 이것의 역순입니다. 이제 dp[i]가 승자가 i 게임을 플레이하는 데 필요한 최소 플레이어 수를 나타낸다고 가정합니다.
• dp 값 사이의 재귀 관계를 dp[i + 1] =dp[i] + dp[i – 1]과 같이 쓸 수 있습니다. 왜냐하면 만약 2위가 (i – 1) 게임을 하고 승자가 i 게임을 했다면 경기에 참가한 모든 플레이어는 서로 연결되어 있지 않으며, 승자가 플레이한 총 게임은 두 세트의 플레이어를 합산합니다.
• 위의 재귀 관계는 dp[i] =dp[i – 1] + dp[i – 2]로 작성할 수 있습니다. 이는 피보나치 급수 관계와 동일하므로 최종 답은 최대 피보나치 수의 인덱스가 됩니다. 입력에 주어진 플레이어 수보다 작거나 같습니다.

예시

#include <bits/stdc++.h>
using namespace std;
int getMaxGamesToDecideWinner(int n) {
   int dp[n];
   dp[0] = 1;
   dp[1] = 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;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Maximum games required to decide winner = 2