[알고리즘 문제풀이] 프로그래머스 - 예상 대진표 / JAVA(자바)

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

코딩테스트 연습 - 예상 대진표

 

/**
    1. 2개를 기준 짝으로, 경기를 치룸.
    
    2. 2의 지수승으로 주어지므로, 부전승은 제외해도 됨.
    
    3. a와 b를 -1한 것이 같은 지수일때, 둘이 붙게 됨.(현재 라운드에서 붙는지 안붙는지 확인 식)
    3-1) (a-1)/2 == (b-1)/2 같으면 둘이 붙는 것
    
    4. 그전까진 n/2 + n%2를 하면서 라운드 증가(다음 라운드 번호 구하는 식)
    
    5. 만약 현재라운드에서 붙는다면, 위의 식을 한번 더하게 되면 같은 숫자가 됨.
    
    6. 이를 이용해 a != b 일때까지 반복시키기
    6-1) 시작라운드가 1이지만, 위의 식을 한번 더 할꺼니까 0에서부터 시작.
    
    5. 최종 라운드 반환


    다른 사람 코드 참조 식..

    Integer.toBinaryString((a-1)^(b-1)).length();

    1. (a-1) XOR (b-1) 을 한것의 length를 구하면 공통조상까지 찾아간 경로의 수가 나온다?

    2. 이해불가..
**/

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;

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

        return answer;
    }
}