목록세그먼트트리 (1)
N coding
2472_체인점
모든 q에 대해 a > x && b > y && c > z인 아이가 하나라도 있는지 확인하는 걸 어떻게 빠르게 할수있나 싶어서 한참 고민하다가 질문검색에서 솔루션을 봤는데 세그먼트 트리를 사용하는 새로운 방식(?)을 안 느낌이었다.진짜 다들 똑똑한듯... 우리가 비교해야하는 변수가 3개뿐이어서 가능한 방법인 것 같다. 1. 일단 A와의 거리를 기준으로 정렬해준다. 이러면 앞에 나오는 A가 자신보다 작거나 같다는 것은 확실해진다.2. B와의 거리를 좌표압축을 하여 세그먼트 트리상의 인덱스로 넘긴다.3. C와의 거리는 세그먼트 트리에 저장되는 값이 된다. 4. 이 때 거리가 0 ~ 자신의 거리 - 1 인 인덱스에 있는 애들 중에 MIN값을 추출해왔을 때 자신의 C보다 작다면 자신은 매장을 설치할 수 없는 구..
PS
2018. 9. 22. 15:02