[백준/BOJ] 백준 17306번 : 전쟁 중의 삶

https://www.acmicpc.net/problem/17306 17306번: 전쟁 중의 삶 석환나라에 전쟁이 일어났다! 석환나라는 엄청나게 큰 이진 트리 모양의 국가로, 1,2, ... ,10100 까지 번호가 붙여진 총 10100 개의 도시로 이루어져 있다. 석환나라에는 10100-1개의 도로가 있는데, www.acmicpc.net 군부대가 있는 도시의 숫자를 2진수 비트로 표현한 뒤, 해당 2진수 비트를 트라이로 표현해서 만들어지는 트라이의 노드의 개수를 구하고 트라이에서 군부대 도시 노드들의 최소 공통 조상(LCA) 노드 위에 있는 노드들(위험하지 않은 도시)의 개수를 빼서 위험한 도시의 개수를 구하는 방법으로 문제를 해결했다. 다음 이미지는 군부대가 있는 도시의 번호가 8,9 일 때 예시이다..

2023.03.30