나는 이 문제를 다음과 같은 사고 과정을 통해 해결했다.
1. 두 숫자가 서로 멀어지면 멀어질수록 나중에 붙는다(라운드 번호가 커진다)
2. 그렇다면 어느정도 멀어질 때 라운드가 커지는가?
3. 토너먼트니까 2의 거듭제곱과 관련이 있지 않을까?
4. 예를 들어, n = 16일 때 1~8과 9~16은 항상 4라운드에서 만난다. 왜?
5. 1~8과 9~16의 차이는 무엇인가. 1을 빼보자.
6. 0~7과 8~15. 0~7은 오른쪽에서 네번째 비트가 0이다. 8~15는 1이다.
7. 서로 다른 최상위 비트를 찾으면 되지 않을까?
8. xor 연산을 사용하면 서로 다를 때 1 같을 때 0을 반환한다는 점을 이용해 두 숫자를 xor한다.
9. 그렇다면 xor 연산을 한 뒤 최상위 비트 1을 찾자.
10. gcc compiler에서 제공하는 __builtin_clz(x)를 사용하면 leading zeros의 개수를 알아낼 수 있고, 그럼 전체 비트 수(int : 32bits)에서 lz를 빼면 내가 원하는 답이다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, a, b;
cin >> n >> a >> b;
cout << 32 - __builtin_clz((a-1)^(b-1));
}__lg(x)를 이용하면 최상위 비트의 인덱스를 얻을 수 있다.
따라서 다음과 같은 코드도 가능하다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, a, b;
cin >> n >> a >> b;
cout << __lg((a-1)^(b-1)) + 1;
}