BOJ 14571 - 모래시계
모래시계의 중심이 되는 점 $u$ 를 고려한다.
이걸 단순히 구하면 시간초과기 때문에 테크닉이 필요하다.
여기서 $u$와 연결되어있고 그 둘도 연결되어있는 쌍 $(a,b),~(a<b)$ 들을 모두 고려한다.
쌍들의 집합에서 $a$가 나오는 횟수를 $c_a$ 라고 할 때, $(a,b)$ 와 서로 다른 어떠한 $(c,d)$ 의 개수를 빠르게 셀 수 있다.
모든 쌍의 개수를 $m$ 이라고 하면 $m-c_a-c_b+1$ 이 그것이다. (포함 배제의 원리)
총 정답에서 $2$를 나눠준 것이 정답이 된다.
Comments