예상 대진표

문제

문제 풀이

1. 문제에서 제시한 대로 8명이 참가했을 때, 각각이 이긴다는 경우로 따져보면 아래와 같은 그림을 그리게 된다.

2. 이렇게 되면 1이 1이 되고, 2가 1이 되고... 7이 4, 8이 4가 된다는 점인데, 계산이 그리 간단하지 않게 된다.

3. 프로그래머에게 익숙한 시작 번호, 0부터 시작한다고 가정하게 되면 값이 깔끔하게 계산된다.

(int 타입은 나눗셈 시 소수점 아래는 제거되기 때문)

4. 반복문을 이용해 answer를 계산해주면 된다.

코드

int solution(int n, int a, int b)
{
    // -1 전처리를 통해 나눗셈 시 숫자가 일치할 수 있도록 변경
    // ex) 1 / 2 => 0, 2 / 2 => 1 ... 불일치
    //     0 / 2 => 0, 1 / 2 => 0 ... 일치
    --a;
    --b;
    
    int answer=0;
    
    // a와 b가 해당 경기 이후 이겼다면 나눗셈으로 인해 값이 같아짐.
    // 따라서 서로 붙은 것으로 해석할 수 있음
    // 4...7인 경우 3번 나눗셈을 한 이후에는 아래와 같이 3번의 나눗셈을 통해서
    // 둘이 같아지게 됨.
    // 3(4에서 전처리)...1...0...0
    // 6(7에서 전처리)...3...1...0
    while(a != b){
        a = a / 2;
        b = b / 2;
        answer++;
    }
    
    return answer;
}

다른 사람의 풀이

1. 동일하게 풀이

2. 전처리 하지 않고 나눗셈 부분에서 +1 처리와 bit shift를 이용해서 풀이