문제

• 예상대진표 문제입니다.
  

  문제 풀기

문제의 평가

• 이 문제는 전형적인 Tree구조의 높이를 찾는 문제입니다.
• A, B는 무조건 승리합니다. 따라서, A/B가 지는 경우는 없습니다.
• 그렇게 하여, A-B가 만나는 대진 높이(A입장에서의 라운드 수)를 계산하는 것이 이 문제의 목표입니다.

해결방안 도출

• 일단, a,b는 1번 시작이기 때문에 0-start로 맞춰서 나누기 연산을 통해 다음 자식을 찾는 접근이 가능하게 합니다. (증명은 생략합니다.)
• while문으로 트리가 0이 되기 이전까지 돌립니다.
• 다음에 만난다는 것은 a,b가 승격했을 때 만나는 것이므로, 만날 때가 되면 return을 시킵니다.
• 그렇지 않다면, a,b모두 /2를 하여 승격시킵니다.
• 승격시에는 답이 1 더해집니다.

해답

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    a -= 1;
    b -= 1;
    while(n != 0) 
    {
        if(a/2 == b/2) {
            answer += 1;
            break;
        }
        
        a /= 2;
        b /= 2;
        n /= 2;
        answer += 1;
    }

    return answer;
}

참고

• 이진트리의 단말노드수는 2^n입니다.
• 비트연산자 쓸 수도 있기는 한데 솔직히 이런것에서 비트연산자를 쓰고 싶지 않습니다.
• 그리고 요즘 컴파일러가 최적화를 잘해줘서... clean code에 위배되는 행위를 하고 싶지 않습니다.

결과