[백준] 23043. 트리 찾기

https://www.acmicpc.net/problem/23043

요약

• 인터렉티브 문제 : 쿼리-결과를 이용해서 정답 찾기
• 쿼리를 통해 트리의 간선을 구하는 문제
• 해석해보면 쿼리로 주어진 노드를 포함하는 가장 작은 트리의 크기를 반환함

접근법

• 두 개씩 쿼리를 줬을때 "2"로 결과를 주면 둘은 간선임. 이렇게 하면 ${N^2}$ 쿼리에 가능은 하지만(모든 경우의 수를 다 해보면 되니까) 주어진 제한 조건은 11111회임
• "1"과 바로 이어져있는 점(간선)은 찾을 수 있음 => 999번 수행
  • 이때 수행결과를 이용하면 깊이를 알 수 있음
  • 즉 1을 루트로 했을때 다른 점까지의 거리로 생각하면 쿼리 결과가 깊이임
• 깊이가 X인 점과 X + 1 인 점이 이어져 있을 것임 => 경우의 수를 줄여서 생각해 볼 수는 있으나 완전 탐색으로 가면 결국 ${499 * 499}$ 쿼리가 나오는 경우도 발생함
• 질문 : 깊이가 X + 1인 점과 이어진 "부모" 노드를 찾을때 깊이가 "X"인 점에 대해서 일일이 쿼리를 다 수행해야할까?

이분탐색

• 깊이가 X + 1인 점 입장에서는 깊이가 X 인 점들이 부모가 될 대상들임
• 깊이가 X + 1인 점을 v, 깊이가 X인 점들 a, b, c가 있고 {루트(1), a, b, c}로 이루어진 그룹의 크기를 R이라고 하면
  • v가 a, b, c중 하나의 자식이라고 하면 {1, a, b, c, v} 그룹의 크기는 R + 1일 것임
  • v가 a, b, c의 자식이 아니라고 하면 {1, a, b, c, v} 그룹의 크기는 R + 1이 아닐것임
    • v 에서 a, b, c를 지나려면 1을 지나야할테고, 1을 지나기 전에 v의 깊이만큼 지날 것임.
    • v의 깊이가 3이상인 경우부터 의미가 있음(2인 경우에는 바로 1과 이어져 있음을 확인할 수 있으므로)
    • 3인 경우 R + 2의 크기를 갖게 될 것이므로, 항상 R + 1보다 크기때문에 R + 1이 되지 않음
• 즉 부모의 범위를 반씩 분할해가면서 해당 영역에 부모가 있는지 판단하는 접근법
  • 해당 영역의 크기가 얼마인지 쿼리
  • v를 포함했을때 크기가 얼마인지 쿼리
• 대략적인 쿼리 수행횟수 : 일렬로 늘어선 경우보다 적당히 뭉쳐진 경우가 높지 않을까..
  • ${1000 = 32 * 32}$ 정도이므로
  • 단계별로 ${32 * log(32) * 2 = 320}$
  • 31 단계로 보면 ${320 * 31 = 9920}$
  • 처음 수행은 대략 1000이므로 ${9920 + 1000 = 10920}$

실제 - 쿼리 수행 초과

• 단계당 333개가 있다고 보면
• 단계별로 ${333 * log(333) * 2 = 333 * 9 * 2 = 5994}$
• 2단계를 수행하면 11988
• 처음 수행 1000을 더하면 12988

쿼리 중복

• 간단하게 생각하면 단계별 최초 쿼리는 0 ~ mid까지에 대한 쿼리일 것이고, 매번 반복됨
• 확장하면 [l][r] 에 대한 쿼리가 중복되므로 저장이 가능함
• 사용했던 쿼리의 결과를 저장해놓으면 쿼리 수행 횟수를 줄일 수 있음