[BOJ 8192] Sheep

#

이 문제는 다각형이 주어질 때, 특정 조건을 만족하는 삼각 분할의 개수를 구하는 문제이다. 어떤 조건은 없다고 쳐도, 삼각 분할을 중복되지 않게 세는 방법은 어떤 것이 있을까? 가장 잘 쓰이는 방법은, 2개의 인자를 두어 생각하는 것이다. 

$count(s, e) := $ $s$, $s+1$, $\cdots$ $e$번 정점으로 이루어진 다각형의 삼각분할의 개수

로 두게 되면, $count(0, n-1)$는 정확히 모든 삼각분할을 담게 된다. 이 때, $count(s, e)$는 $s+1$에서 $e-1$ 사이의 어떤 정점 $i$에 대해 $s$, $i$, $e$로 삼각형을 만들게 되면 $count(s, i) \times count(i, e)$로 나누어진다. 즉, 

$$count(s, e) = \sum_{i=s}^{e} count(s, i) \times count(i, e)$$

이다. 만약 $s>e$인 경우에는, $i=$ $s+1$, $\cdots$, $n$, $1$, $\cdots$, $e-1$에 대해 생각해야 할 것이다. 이제, 문제는 DP로 풀렸다.

이 문제에서 주고 있는 제약은 '각 삼각형은 짝수 개의 spot을 담아야 한다'는 것이다. 여기서 내 처음 생각과 나중의 생각이 갈린다. 처음 생각은 각 삼각형에 대해 포함하는 spot의 개수를 빠르게 구할 수 있게 전처리하자는 것이었다. 전처리가 완료되었다면, 위의 점화식에서 삼각형 $s, i, e$가 만들 수 있는 삼각형인 경우에 대해서만 생각하면 되기 때문이다.

$a, b, c$가 이루는 삼각형에 대해, 삼각형 밖에 있는 spot은 세 종류가 있다. 각각 $ab$, $bc$, $ca$ 선분 밖에 있는 spot들이다. 각각에 대해 '선분 밖에 있는 spot의 개수'를 알 수 있으면, 세 선분에 대해 계산해 2로 나눈 나머지를 합한다. 문제가 간략해졌다. 질문 "선분이 주어질 때, 선분 밖의 spot의 개수는 몇 개인가?"를 빠르게 해결하면 된다. 모든 정점 $P$에 대해 spot $S$들을 $PS$의 기울기 순서대로 정렬한 결과 인덱스 배열을 전처리해 둔다. 그 후 이분탐색으로 선분 한 쪽 점에서 반대쪽 점을 찾으면, 한 쪽 방향에 있는 spot의 개수를 알 수 있다.

이 방법은 전처리에 $O(nk\log k)$, DP에 $O(n^2 \log k)$를 사용해 $O(n(n+k) \log k)$의 시간 안에 작동한다. 하지만 상수가 커서 시간 안에 나오지는 않았다. 시간을 잘 커팅하면 되겠지만, 잘 떠오르지 않았다.

이 때의 두 번째 풀이는 alpah가 먼저 생각한 것이다. 어떤 선분이 삼각분할 안에 포함되었다면, 선분으로 spot들이 짝수 개씩 나뉠 것이다. 이를 이용해 각 선분의 포함 가능성 여부를 전처리해 두면(이 또한 각 정점에 대해 spot을 기울기 순으로 정렬함으로 얻을 수 있다. 하지만 이 때는 정렬 결과를 직접 저장할 필요는 없을 것이다) 삼각형이 포함 가능한지는 간단히 삼각형을 이루는 각 선분들이 포함 가능한지와 동치가 된다. 전처리의 시간 복잡도는 같지만 DP에 $O(n^2)$만의 시간을 사용해, $O(n^2 + nk\log k)$ 시간에 돌아간다. 상수 또한 몇 배 작고. 멋진 방법이지만, 사실 첫 방법이 안 되는 것은 아직도 불합리하다고 생각하고 있다.