[C++] 백준 BOJ 1057 토너먼트

문제링크 : https://noj.am/1057

문제의 조건에서 지민과 한수가 둘이 만나기 전까지는 무조건 이긴다고 하였다.

따라서 문제에서 나온 조건대로 하면 '만약 서로 대결하지 않을 때는 -1을 출력한다.'은 절대로 나올 수 없기 때문에 무시해도 된다.

두 사람이 만날 수 있는 조건은 A와 B가 각각 2n-1과 2n 이어야 하는 조건이다.

계산을 편하게 하기 위해서 그냥 A, B를 작은 순서대로 정렬하고 A가 홀수이고 A-B의 차가 1이면 정답으로 출력하도록 했다.

두 사람이 각 라운드에서 만나지 못한다면 div( ) 함수를  통하여 입력값을 절반으로 나누어주면서 정답을 찾아가면 된다.

절반씩 계속 나누기 때문에 최악의 경우에도 O(logN)의 시간복잡도를 보일 것이다.

// BOJ_1057 토너먼트
#include <iostream>
 
using namespace std;
 
// 입력 값을 절반으로 나누고
// 홀수면 +1을 더해준 값으로 반환
int div(int n) {
    return n % 2 ? n / 2 + 1 : n / 2;
}
 
// 작은 숫자가 a, 큰 숫자가 b가 되도록 정렬(스왑)
int sort(int &a, int &b) {
    if (a > b) {
        int temp = a;
        a = b;
        b = temp;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int num;
    int person1, person2;
    cin >> num >> person1 >> person2;
 
    sort(person1, person2);
    int round = 0;
 
    while (true) {
        round++;
        // person1이 홀수이고 person2와의 차가 1이면
        if (person1 % 2 && person2 - person1 == 1)
            break;
 
        // 다음 라운드로 진출 시 숫자를 절반으로 나눔
        person1 = div(person1);
        person2 = div(person2);
    }
    cout << round;
 
    return 0;
}

더 쉬운 방법으로는 각 숫자를 1씩 빼줘서 1~N 범위의 숫자를 0~N 범위로 만든 다음에 2n과 2n+1일때의 case를 찾으면 더 간단하게 풀린다. 

// BOJ_1057 토너먼트
#include <iostream>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int num;
    int person1, person2;
    cin >> num >> person1 >> person2;
 
    // 1~N 범위를 0~N-1로 변환
    person1--;
    person2--;
 
    int round = 0;
    // 두 수가 각각 2n과 2n+1이면 정답
    // 이때, 2로 나눴을 때 두 수가 같아지므로 탈출 조건으로 설정
    while(person1 != person2){
        round++;
        person1 >>= 1;
        person2 >>= 1;
    }
    cout << round;
 
    return 0;
}