가까운 만유인력 (BOJ 9482)

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

Solution 1 :

원으로 생각하면 골치아프니 (x, y, z)를 중심으로 하는 2k 길이의 정육면체를 생각하고, 여기 안에 있는 점들을 일일히 순회한다.

순회를 할 수 있다고 치면 복잡도는 얼마일까? 답에 도움이 안되는 점들은 정육면체 - 구 영역에 존재할 것이다. 이러한 영역은 8개이며, 8개 영역 각각에 속하는 모든 점들은 서로의 거리가 K 이하이다. 고로 각 영역에 이러한 점들은 많아야 O(sqrt(ans))개. 순회만 할수 있으면 된다.

순회를 하는 건.. z축 기준으로 스위핑을 하며, 스위핑 과정에서 세그트리 + std::set을 사용했다. std::set은 y축 기준 정렬, 세그트리는 x축 기준이고, x축은 이 때문에 약간의 좌표압축을 가해줬다. 뭐.. 딱히 길지는 않다. 순수 스위핑은 O(Nlg^2N)으로 꽤 빠르게 동작한다.

Solution 2 :

[x / K, y / K, z / K] 기준으로 버킷을 만들어 준다.버킷 내부의 원소는 많아야 O(sqrt(ans))개. 점 하나와 거리 K 이하인 점은 인접한 버킷 27개를 봐주면 구할 수 있다. 버킷의 인덱스가 과다하긴 한데 std::map같은 걸로 해결 가능.

solution 1을 보고 solution 2를 확인했다. 이렇게 보니 훨씬 생각하기 쉬운 문제인데 너무 어렵게 생각했다 ㅠㅠ