문제
https://www.acmicpc.net/problem/3049
모든 내부각의 180°보다 작은 다각형을 볼록 다각형이라고 한다.
세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세어라.
풀이
조합 공식을 활용하면 간단하게 문제를 해결할 수 있다.
하나의 교차점이 생기기 위해서는 4개의 꼭짓점을 선택해야 한다. 그 경우의 수를 조합 공식으로 나타내면 \(_{n}\mathrm{C}_{4}\)에 해당한다. 이것을 정리하며 아래와 같다.
$$ \begin{matrix} _{n}\mathrm{C}_{4} &=& {n! \over 4!(n-4)!} \\ &=& {n(n-1)(n-2)(n-3)(n-4)(n-5)\cdots \over 4 * 3 * 2 * 1(n-4)(n-5)\cdots} \\ &=& {n(n-1)(n-2)(n-3) \over 4 * 3 * 2 * 1} \\ &=& {n(n-1)(n-2)(n-3) \over 24} \end{matrix} $$
도출해낸 공식을 코드로 나타낸다.
import sys
n = int(sys.stdin.readline())
print(n * (n - 1) * (n - 2) * (n - 3) // 24)
참고 문서