일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 2794
- 14179
- 기하 알고리즘
- BAPC
- 구현
- ICPC 연습
- 세그먼트 트리
- boj
- 백준 온라인 저지
- codeforces
- 8192
- DP
- 코드포스
- acmicpc.net
- Z algorithm
- Divide and conquer optimization
- BAPC 2018
- 그래프
- 볼록 껍질
- POI Solution
- IOI 2013
- 기하
- Implementation
- JOI
- Manacher's algorithm
- Manacher 알고리즘
- JOI 2018
- 컨벡스 헐
- Z 알고리즘
- convex hull
- Today
- Total
프로그래밍 연습장
[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)$ 시간에 돌아간다. 상수 또한 몇 배 작고. 멋진 방법이지만, 사실 첫 방법이 안 되는 것은 아직도 불합리하다고 생각하고 있다.
'문제 해결 > acmicpc.net' 카테고리의 다른 글
[BOJ 9521] 색칠 공부 (0) | 2017.10.22 |
---|---|
[BOJ 7332] 편의점 알바 (0) | 2017.08.28 |
[BOJ 8874] 웜뱃 (0) | 2017.08.27 |
[BOJ 14179] 크리스마스 이브 (0) | 2017.08.18 |
[BOJ 2794] MARS (0) | 2017.03.25 |