[C++] 예상 대진표

 

 

예상 대진표

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다

 

 

 

입출력 예

 

n = 8

a = 4

b = 7

출력 = 3

 

예를들어 8명이 참가할 경우, 첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

 

 

 

8명의 대진표를 그림으로 그려보면,

첫 라운드에서 1 과 2 중 우승한 사람이 1번,

3번 / 4번 중 우승한 사람이 2번, 

5번 / 6번 중 우승한 사람이 3번,

...

n-1번 / n번 중 우승한 사람이 n번을 가지게 됩니다.

 

 

그래서 C++의 나누기 연산의 성질과 위 규칙을 이용하면, 각 번호에 1을 더한뒤 2로 나눠주면 다음 라운드의 번호와 같아지게 됩니다.

왜냐하면 2와 3을 2로 나누는 (2 / 2),  (3 / 2)는 모두 1을 출력하기 때문입니다.

 

또한, 입력으로 주어진 a, b 가 같아지게 되는 라운드의 이전 라운드가 두 번호가 붙는 라운드입니다.

 

 

 

따라서 위 두가지를 조합하면 다음과 같은 코드를 만들고 a, b 가 같아질때 까지 다음과 같이 반복을 하면서 라운드를 더하면 됩니다.

 

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int round = 0;
    while(a != b){
        round++;
        a = (a + 1)/2;
        b = (b + 1)/2;
    }
    return round;
}