[백준(JAVA)] 13116번: 30번

문제

✔ 난이도 - Silver 4

http://wdown.ebsi.co.kr/W61001/01exam/20061116/mathga1_mun.pdf

설명

완전 이진 트리에서 두 노드 a와 b가 주어졌을 때, 그 둘의 공통 조상 k를 찾는 문제이다.
각 노드 x의 부모 노드의 값은 x / 2이므로 a와 b의 부모 노드를 따라가다보면 공통 노드를 발견할 수 있게 된다.
a와 b 중 큰 수의 부모노드를 찾아 그 값으로 대체하는 작업을 a와 b가 같아질때까지(공통 노드 발견) 반복한다.

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        StringTokenizer st;
        int a, b;
        for (int i = 0; i < T ; i++){
            st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            sb.append(getLCA(a, b) * 10).append("\n");
        }

        System.out.println(sb);
    }

    public static int getLCA(int a, int b){
        while (a != b){
            if (a > b){
                a /= 2;
            } else {
                b /= 2;
            }
        }

        return a;
    }
}

TIL💡

📌 트리에서 공통 조상 ? LCA(Lowest Common Ancestor) !!