[백준 13116번] 30번 (C++)

문제링크 : https://www.acmicpc.net/problem/13116

13116번: 30번

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, A, B;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    while(T--)
    {
        cin >> A >> B;

        while(A!=B) //서로 만날 때까지 (조상노드가 같을 때까지)
        {
            if(A>B) A=A/2; //큰 값 기준으로 부모노드 찾기
            else B=B/2;
        }
        cout << A*10 << "\n"; 
    }
    return 0;
}

최소 공통 조상 문제를 골드에서 처음 접하여 실버에서는 어떤 난이도인지 궁금해서 풀게된 문제이다.

해당 문제의 트리 그림을 보면 완전 이진 트리인 것을 알 수 있다.

완전 이진 트리의 부모의 위치는 자식 / 2이다.

이를 이용하여 입력받은 A, B가 같아질 때 까지 큰 값을 기준으로 2를 계속 나누며 조상 노드를 찾아나가면 된다.

 

이후 출력은 문제에서 K*10을 하도록 했으므로 A or B에 10을 곱해서 출력해준다.