[BOJ 3049] 다각형의 대각선

3049번: 다각형의 대각선

문제 분석

• 도형에서 대각선의 교차점이 생기기 위한 조건 : 꼭짓점 4개
  - 대각선의 교차점이 생기기 위해서는 두 대각선이 필요하다.
  - 두 대각선이 존재하기 위해서는 꼭짓점 4개가 필요하다.

풀이 방식

• n각형의 꼭짓점 갯수는 n개, 그중 4개를 뽑는 경우는 nC₄ 로 표현 가능 하다.
• nC₄ = n!/(n-4)!4! = n(n-1)(n-2)(n-3)/24

#include <iostream>

using namespace std;

int n, meet = 1;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    if (n < 4) {
        cout << 0;
        return 0;
    }
    for (int i = 0; i < 4; i++) {
        meet *= (n - i);
    }
    meet /= 24;
    cout << meet;
    return 0;
}

느낀 점

• 수학 공식을 알고 풀면 금방 푸는 문제다.
• 처음엔 대각선의 개수를 구하고 대각선 중 2개를 고르려 했지만 서로 만나지 않는 경우가 있으므로 이 방법은 틀렸다.
• 사각형의 교차점의 개수가 1개라는 부분에서 큰 힌트를 얻었다.

시간복잡도  : O(1)