석환나라에 전쟁이 일어났다! 석환나라는 엄청나게 큰 이진 트리 모양의 국가로, 1,2, ... ,10^100 까지 번호가 붙여진 총 10^100 개의 도시로 이루어져 있다. 석환나라에는 10100-1개의 도로가 있는데, 이 중 i번째 도로는 (1 ≤ i <10^100) floor(i+1 / 2)번 도시와 i+1 번 도시를 잇는데, 이를 그림으로 묘사하면 아래와 같다:
총리 윈스턴 아기서콴(Winston Agiseokhwan)은 위기의 석환나라를 구하는 중대한 임무를 맡고 있다. 석환나라의 적국들은 석환나라의 중요 군 시설을 방해하는 데 혈안이 되어 있기 때문에, 석환나라의 국민들을 보호하기 위해서는 군대가 자주 오가는 도시를 우선 방어하는 것이 효과적이다. 석환나라에는 N개의 군부대가 서로 다른 도시에 존재하고, 군부대들은 서로 물자나 정보를 주고받기 위해서 오간다.
이때, 어떠한 도시가 위험하다는 것은, 해당 도시에 군부대가 있거나, 경로가 해당 도시를 지나는 서로 다른 두 군부대가 존재함을 뜻한다. 석환나라는 트리이고, 경로는 같은 도시를 두 번 방문하지 않아야 한다고 정의되기 때문에, 두 군부대를 지나는 경로는 언제나 유일하다는 사실을 유념하자.
이후 N개의 줄에 군부대가 있는 도시의 번호를 나타내는 수열 A1, ..., AN이 주어진다. 주어지는 도시들은 서로 다르다. (1 ≤ Ai < 2^50)
출력
석환나라에 있는 위험한 도시의 개수를 출력하라.
입력 예시
4
4 5 6 7
출력 예시
7
풀이
우선, N개의 모든 도시의 최소 공통 조상(LCA)을 구해야 한다. 즉 N개의 도시에 주둔한 군대는 LCA 루트 노드를 방문하는 경로를 가지게 된다. 또한 위험한 도시들은 이 LCA 노드를 루트로 하는 이진 트리 형태를 띈다. 본 트리가 이진 트리이므로 시프트 연산을 통해 간단하게 부모 노드를 방문할 수 있다.
그 다음 N개의 도시를 루트 노드까지 방문하며, 방문한 총 노드 수가 우리가 구하는 값이 된다. Ai의 값은 최대 2^50이므로 높이는 그 로그값인 50이다. LCA를 구하는 경우와 루트까지의 방문 모두 O(NlogN) 시간복잡도가 소요된다.
p.s. 루트 노드를 구하는 과정에서 방문 여부를 갱신하면 중복 연산을 줄일 수 있겠다.
풀이 코드
N = int(input())
nums = list(map(int, input().split()))
visit = set()
def find_lca(a, b) :
ad = len(bin(a))-2
bd = len(bin(b))-2
visit.add(a)
visit.add(b)
if ad > bd :
a, b = b, a
for _ in range(abs(bd - ad)) :
b >>= 1
visit.add(b)
while a != b :
a, b = a >> 1, b >> 1
visit.add(a)
visit.add(b)
return a
root = find_lca(nums[0], nums[1])
for i in range(2, N) :
root = find_lca(root, nums[i])
print(len(visit))
