[프로그래머스] 예상 대진표 with C++

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　

　다음 그림처럼 토너먼트 브라켓 구조를 띄고 있는 대회에서 A참가자와 B참가자가 무조건 이긴다는 가정 하에 몇 번째 라운드에서 만날지 예측하는 문제다. 배열을 갱신하며 두 특정 참가자가 만나는 시점까지 반복하는 방법과, 두 참가자의 위치를 업데이트하고, 이들이 같아질 때까지 라운드를 증가시키는 방법이 존재한다.

---

풀이 (1) 배열 갱신

#include <vector>
using namespace std;

int solution(int n, int a, int b)
{
    int cnt = 1;
    vector<bool> v(n, 0), tmp;
    v[a - 1] = true; v[b - 1] = true;

    for (int i = 0; i < n; i += 2)
    {
        if (v[i] && v[i + 1] == true)
            return cnt;
    }

　벡터를 초기화하고, 참가자 a와 b의 위치에 true로 초기화한다. 그리고 첫 번째 라운드에서 두 참가자가 만나는지 확인한다.

 

    while (true)
    {
        tmp.clear();
        cnt++;

        for (int i = 0; i < n; i += 2)
            tmp.push_back((v[i] || v[i + 1]));

        for (int i = 0; i < tmp.size(); i += 2)
        {
            if (tmp[i] && tmp[i + 1] == true)
                return cnt;
        }

        swap(v, tmp);
        n /= 2;
    }
}

　그 후 두 참가자가 만날 때까지 벡터를 초기화하며 서로 만났는지 확인하면 된다.

 

총합본

#include <vector>
using namespace std;

int solution(int n, int a, int b)
{
    int cnt = 1;
    vector<bool> v(n, 0), tmp;
    v[a - 1] = true; v[b - 1] = true;

    for (int i = 0; i < n; i += 2)
    {
        if (v[i] && v[i + 1] == true)
            return cnt;
    }

    while (true)
    {
        tmp.clear();
        cnt++;

        for (int i = 0; i < n; i += 2)
            tmp.push_back((v[i] || v[i + 1]));

        for (int i = 0; i < tmp.size(); i += 2)
        {
            if (tmp[i] && tmp[i + 1] == true)
                return cnt;
        }

        swap(v, tmp);
        n /= 2;
    }
}

---

풀이 (2) 위치 갱신

using namespace std;

int solution(int n, int a, int b)
{
    int cnt = 0;
    a--; b--;

    while (a != b) 
    {
        a = a / 2;
        b = b / 2;
        cnt++;
    }

    return cnt;
}

　이진 토너먼트의 구조를 이용하여 a와 b가 같은 라운드에서 만나게 될 때까지 진행하면 된다. 각 참가자의 번호를 2로 나눈 것은, 다음 라운드에서의 위치를 의미한다. 이렇게 하면 각 참가자는 다음 라운드에서 자신의 번호를 2로 나눈 위치에 배치하게 된다. 예를 들어, 참가자 4와 5는 처음에는 다른 경기에서 경쟁하지만, 다음 라운드에서는 같은 경기에서 만나게 된다.