25/03/19 - 예상 대진표(c++)

예상 대진표(https://school.programmers.co.kr/learn/courses/30/lessons/12985)

 

해당 문제는 토너먼트 형식으로 진행되는 대회에, A와 B가 참가하게 되면 몇 라운드에 마주치게 될 것인지 구하는 문제이다. 이때, 두 사람은 서로 붙게 되기 전까지 항상 이긴다고 가정한다.

 

여기서 N명의 참가자는 각각 1 ~ N번을 차례대로 배정받는다. 그리고 1번은 2번과, 3번은 4번과... N-1번 과 N번이 싸우게 된다. 그렇게 게임 결과가 나오면, 승자들은 다시 1 ~ N/2번을 차례대로 배정받는다.

그리고 N은 2의 지수 승으로 주어지므로 부전승은 발생하지 않는다.

 

따라서 여기서 생각할 건 다음과 같다.

 

1. N명의 참가자들이 모였을 때, 최대 라운드는 N의 이진로그이다.

(2^n <= 여기서 n이 최대 라운드)

 

2. A < B 일 수 있고, 반대로 A > B 일 수 있다.

이는 즉, A - B 를 진행할 때 답이 -1이 될 수도, 1이 될 수도 있다는 뜻이다.

 

3. 다음과 방식으로 A와 B가 서로 인접해 있는 경우는 무시한다.

A = 2, B = 3

(무시하는 이유: 1과 2, 3과 4끼리 싸워야 하므로.)

 

이를 기반으로 코드를 작성하면 다음과 같다.

#include <iostream>
#include <cmath>

using namespace std;

int numSet(int num) {
    return num / 2 + (num % 2);
}

int solution(int n, int a, int b)
{
    int answer = 1;
    int round = log2(n);
    int nA = a, nB = b;
    
    cout << round << endl;
    for(answer; answer<round; answer++) {
        int del = nA - nB;
        
        if((del == 1 && (nA % 2 == 0)) || (del == -1 && (nB % 2 == 0)))
        {
            break;
        }
        
        nA = numSet(nA);
        nB = numSet(nB);
    }

    return answer;
}

 

여기서 del == 1 && (nA % 2 == 0) 부분과 del == -1 && (nB % 2 == 0)을 조금 더 설명하자면, 다음과 같다.

 

서로가 바로 다음 순서일 때, A와 B가 토너먼트에서 만났음을 알 수 있다.

그러나 2와 3처럼, 서로가 바로 다음 숫자여도 만나지 못하는 경우가 있다. 이를 판단하기 위해 if문을 작성했다.

 

코드의 내용을 좀 더 설명하자면, A와 B가 서로 인접한 숫자이고, A < B일 때, A - B를 실행하면 -1이 나온다.

이 상태에서 A와 B가 시합을 하는 숫자 조합은 1과 2, 3과 4, 5와 6... 이런 식이다. 즉, A는 홀수여야하고, B는 짝수여야 한다.

그러니 A = 2, B = 3 처럼, 인접하되 경우가 맞지 않는 걸 찾기 위해 해당 if문을 사용했다. 이는 반대로 A > B일 때, A - B를 실행하면 1이 나올때도 마찬가지다.