[BOJ3049] 다각형의 대각선

[BOJ3049] 다각형의 대각선

문제 링크

---

코드 리뷰

• 점화식 찾는 연습하기 위한 정답률 50퍼센트 이상을 찾아보았다.
• 다각형이 주어질때, 그 다각형의 대각선을 그리고, 대각선들끼리 교차하는 점의 개수를 찾는 문제였다.
• 점이 만들어지기 위해서는, 대각선 두개가 필요하고, 각 대각선은 서로 다른 대각선의 꼭지점이 2개씩 필요하다.
• nC4 조합을 통해 순서 없이 다각형의 꼭지점중 4개를 뽑으면 답이 나온다.

---

/* BOJ 3049 다각형의 대각선 */
#include <iostream>
using namespace std;

int comb(int n, int k) {
	if (k == 1) return n;
	if (n == k) return 1;
	return comb(n - 1, k) + comb(n - 1, k - 1);
}
int main() {
	int N;
	cin >> N;
	cout << comb(N, 4);
	return 0;
}

---