프로그래머스: 예상 대진표

import java.util.*;

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

    public static void main(String[] args) {
        int N = 8;
        int A = 4;
        int B = 7;
        
        Solution sol = new Solution();
        int result = sol.solution(N, A, B);
        System.out.println(result); 
    }
}

총 8명이 있을 때 4번 선수와 7번수가 만날 수 있는 라운드를 묻는 것이다.

4번 선수와 7번 선수를 서로 만나기 전까지 항상 이긴다.

바로 이전 라운드에서 이긴 참가자들은 다음 라운드에서 새로운 번호를 부여받는데, 이때 번호는 항상 이전 번호의 절반(소수점 올림)으로 새로 부여된다.

예를 들어, 1번과 2번 참가자가 경기를 치뤘을 때 이긴 참가자는 다음 라운드에서 1번을 부여받게 됩니다. 이는 (2 + 1) / 2 연산을 통해 얻어진다.

따라서, a와 b에 대해 (a + 1) / 2와 (b + 1) / 2 연산을 수행하는 것은 다음 라운드에서 a와 b 참가자가 받게 될 새로운 번호를 계산하는 것이다!

이렇게 각 라운드마다 a와 b의 번호를 업데이트하면서 a와 b가 같아질 때까지 반복하면, a와 b가 같은 라운드에서 만나는 순간을 알 수 있다.