백준 - 1057 토너먼트

https://www.acmicpc.net/problem/1057

1057번: 토너먼트

---

풀이 방법

오랜만에 돌아온 백준 문제 풀이!!

최근에는 알고리즘 잡스 문제를 풀기 때문에 백준 알고리즘 문제 풀이 글이 줄어들었다ㅠㅠ

 

여튼 이번 문제의 핵심 포인트는 a 와 b 가 같은 라운드에 언제 만나는지 확인하는 것 이다.

따라서 '같은 라운드' 를 확인하는 방법을 알아야한다.

 

같은 라운드에 있다는 걸 확인하는 방법은 아주 간단하다.

(a+1)/2 의 값과 (b+1)/2 의 값이 같은지 여부를 확인하면 된다. 이는 1 과 2, 3과 4 ---에 대해서 계산해보면 놀랍게도 같은 값이 나오게 된다.

 

이 방법을 이용하면 코드는 정말 쉽게 짤 수 있다. 심지어 n은 필요도 없다

/*
    이 문제의 포인트는 a 와 b 가 한 라운드에 있는 경우를 찾는 것이다.
    여기서 한 라운드란 a+1/2 했을 때와 b+1/2 했을 때 같은 값이 나오는 때를 의미한다.
    이는 1, 2 가 있을 때 1+1/2 == 1 , 2+1/2 == 1 햇을 때 값이 같고,
    3+1/2 ==2 , 4+1/2 == 2 -----> 로 같기 때문이다.
*/
public class Quiz_1057 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        sol(n, a, b);
    }

    static void sol(int n, int a, int b){
        int answer = 0;

        while (a!=b) {
            answer++;

            a+=1;
            a = a/2;

            b+=1;
            b = b/2;
        }

        System.out.println(answer);
    }
}