3049번 - 다각형의 대각선
저는 머리를 쥐어짜면서 간신히 문제를 풀었는데
다른 분들은 죄다
N * (N - 1) * (N - 2) * (N - 3) / 24
라는 식으로 문제를 풀으셨더군요...
이 식이 어떻게 문제의 답을 구하는지 제 머리로는 도저히 이해할 수 없습니다.
문제풀이 고수님들 설명좀 해주세요 ㅠㅠ
n*(n-1)*(n-2)*(n-3)/24=nC4이죠?
n개의 꼭지점을 가진 볼록 다각형에서 4개의 점을 잡으면 하나의 볼록 사각형을 만들 수 있고, 해당 볼록 사각형은 단 하나의 대각선의 교점을 가지죠.
따라서 볼록사각형을 몇 개 만들 수 있는지 알면 대각선들의 꼭지점의 총 개수도 구할 수 있겠죠
적고 보니 엄밀하지 못한 듯 해서 더 적을게요ㅋㅋㅋ
대각선의 교점은 두 대각선으로 이루어지고, 각 대각선들은 해당 다각형의 서로 다른 두 꼭지점들로 구성되죠.
따라서 대각선의 교점 하나는 다각형들의 꼭지점 4개의 조합으로 표현되며, 이 조합은 유일합니다.
따라서 n개의 꼭지점 중에 4개의 꼭지점을 순서없이 고르는 연산을 하면 되니 답은 nC4가 되겠죠
감사합니다!
쉽게 설명을 해주셔서 금방 이해가 됐네요
덕분에 편히 잘 수 있을 것 같습니다!
댓글을 작성하려면 로그인해야 합니다.
wxogus25 8년 전
저는 머리를 쥐어짜면서 간신히 문제를 풀었는데
다른 분들은 죄다
N * (N - 1) * (N - 2) * (N - 3) / 24
라는 식으로 문제를 풀으셨더군요...
이 식이 어떻게 문제의 답을 구하는지 제 머리로는 도저히 이해할 수 없습니다.
문제풀이 고수님들 설명좀 해주세요 ㅠㅠ