문제
볼록 N각형의 대각선들이 내부에서 만드는 교차점의 수를 구하라. 세 대각선이 한 점에서 만나지 않는다고 가정한다.
입력
꼭짓점의 수 N이 주어진다 (3 이상).
출력
대각선의 교차점 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 | 15 |
풀이
조합 공식을 이용하여 교차점 수를 계산한다.
- 볼록 다각형에서 4개의 꼭짓점을 선택하면 정확히 하나의 교차점이 생긴다
- 따라서 교차점 수는 C(N, 4) = N(N-1)(N-2)(N-3) / 24이다
핵심 아이디어: 두 대각선이 내부에서 교차하려면 서로 다른 4개의 꼭짓점을 양쪽 끝점으로 가져야 하므로, 4개 꼭짓점 조합 수가 교차점 수와 같다.
코드
n = int(input())
print(int(n * (n - 1) * (n - 2) * (n - 3) / 24))복잡도
- 시간: O(1)
- 공간: O(1)