[백준/boj] 13116: 30번 (Java) - 트리 / 구현

문제

풀이

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int A, B;

    public static void main(String[] args) throws Exception {

        int T = Integer.parseInt(br.readLine());
        for (int i = 1; i <= T; i++) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            int minNum = Math.min(A, B);
            if(minNum == A) { 
                while(true) { // 1.
                    if(B - A < A) break;
                    B/=2;
                }
            } else {
                while(true) {
                    if(A - B < B) break;
                    A/=2;
                }
            }

            while (A != B) { // 2.
                if(A > B) {
                    A /= 2;
                    if(A== B) break;
                    B /= 2;
                }
                else {
                    B /=2;
                    if(A == B) break;
                    A/=2;
                }
            }
            bw.append((A*10)+"\n");
        }
        bw.flush();
        bw.close();
    }
}

1. A와 B 중 더 작은 값을 기준으로 높이의 차가 1이하가 될때까지 큰 값을 부모 노드로 이동시키는 코드이다.

• 이때, 큰 값에서 작은 값을 뺀 값이 작은 값보다 작아질때까지 큰 값을 2씩 나눈다(부모 노드로 이동한다.) ==> 높이의 차를 1 이하로 만들어준다.
• 높이가 1 차이나는 경우 : 만약 `A`가 7이고, `B`가 8인 상황에서 1번을 돌고 나면 7과 8이 그대로 유지된다. 7과 8은 다른 높이 이지만 높이의 차가 1 이하이므로 2번에서 해결해 줄 것이니 괜찮다.

2. A와 B 중 더 큰 값부터 2씩 나누면서(부모 노드로 이동) 값이 같아지면 그 값 *10을 반환한다.