[BOJ 3049 // C++] 다각형의 대각선

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3049번 문제인 다각형의 대각선이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/3049

3049번: 다각형의 대각선

 

이 문제는 길이가 N인 다각형의 대각선의 교점의 개수를 세는 문제이다.

 

방법1) 처음에 풀어서 제출한 방법이다.

1. N각형의 꼭짓점 X를 하나 고른다. 나머지 꼭짓점을 반시계방향으로 1, 2, ... , i, ... , N-1이라 이름붙이자.

2. X와 꼭짓점 i를 잇는 대각선이 만드는 교점의 개수는 이 대각선으로 양옆으로 나뉜 점들의 개수와 같다는 것을 간단한 관찰을 통해 알 수 있다. 즉, X와 i를 잇는 대각선은 교점 (i-1) * (N-1-i) 개이다. 이를 각 꼭짓점 i마다 계산하여 더한 값을 구한다.

3. 모든 꼭짓점에 대해서 그 꼭짓점이 연결된 대각선이 포함된 교점의 개수는 2에서 구한 값과 같다. 교점마다 두 대각선의 시작점과 끝점으로 선택하는 순서를 바꾸경우가 존재하므로, 답은 (2에서 구한 값) * N / 4가 된다.

 

방법2) 대각선의 교점을 이루는 네개의 점의 개수를 세는 방법

잘 관찰해보면, 각 대각선의 교점과 그 교점을 이루는 두 대각선의 끝 네 점을 고르는 방법은 일대일대응이 된다. 따라서, 다각형의 대각선의 교점의수는 다각형의 꼭짓점 중 네개의 꼭짓점을 고르는 경우의 수와 같다는 것을 알 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main()
{
    long long N; cin >> N;
    cout << N * (N - 1) * (N - 2) * (N - 3) / 24;
}