문제

https://school.programmers.co.kr/learn/courses/30/lessons/12985

---

입력

• 게임 참가자 수 N
• 참가자 번호 A
• 경쟁자 번호 B

---

출력

• A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지

---

풀이

제한조건

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

접근방법

단순 계산

A번 참가자와 B번 참가자는 항상 승리한다. 라는 조건을 유심히 생각해보자.
대결은 항상 토너먼트로 이루어 지므로, 절반씩 참가자가 줄어든다.

이진 트리의 형태로 생각해보자.

각 라운드의 승리자가 상위로 올라간다고 정리하면,
현재 참가자 번호를 절반으로 나누고 +1을 해준다면 다음 라운드에서 만나는지 확인할 수 있다.

---

코드

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;
        while(a != b){
            a = (a-1) / 2 + 1;
            b = (b-1) / 2 + 1;
            answer++;
        }
        return answer;
    }
}