[Silver V] 다각형의 대각선 - 3049 (수학)

[Silver V] 다각형의 대각선 - 3049

문제 링크

성능 요약

메모리: 30840 KB, 시간: 68 ms

분류

조합론(combinatorics), 수학(math)

문제 설명

세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오.

아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다.

모든 내부각이 180도보다 작은 다각형을 볼록 다각형이라고 한다.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 100)

출력

첫째 줄에 교차점의 개수를 출력한다.

n = int(input())
print(int(n*(n-1)*(n-2)*(n-3)/24))

수학 문제라 생각했지만, 공식을 찾지 못해 빠르게 포기.

결론은 n각형이 있을 때 꼭짓점 하나가 만나려면 4개의 점이 필요하다는 점이었다.

해당 공식을 통해 nC4를 해주면 문제를 해결할 수 있었다.