[BOJ]13116번: 30번

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

---

수학 문제입니다.

 

최대 1024개의 노드가 있을 때 임의의 두 수가 주어지면 최대 공통 조상을 찾아야 합니다.

 

최대 공통 조상을 찾는 방법은 힙의 원리처럼 주어진 수 / 2 를 계속해서 1까지 가보면 거쳐가는 모든 수가 자신의 조상 노드입니다.

 

쿼리가 최대 5만개이고, 하나의 쿼리를 처리하는데 걸리는 시간은 O(10) 입니다. 

(최대 노드 크기가 1023이고 1023도 2^10 이기 때문에 나누기 2 연산의 최대 깊이는 10을 넘지않습니다.) 

 

문제를 해결하는 방법은 여러가지입니다.

저는 주어진 수를 작은 수, 큰 수로 나눴고 작은 수가 거쳐간 모든 조상을 표시한 뒤, 큰 수의 모든 조상을 구하면서 한 번이라도 작은 수의 조상과 일치하면 그 조상을 최대 공통 조상으로 리턴하면 됩니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ13116.java