C++로 n변 볼록 다각형의 대각선 개수 구하기

문제 이해하기

정수 n이 주어졌을 때, n변 볼록 다각형(convex polygon)의 대각선 개수를 구하는 문제입니다. 예를 들어 n = 5인 오각형이라면 대각선의 개수는 5개입니다.

접근 방법

n변 볼록 다각형에서 각 꼭짓점은 자기 자신과 양옆에 인접한 두 꼭짓점을 제외한 나머지 꼭짓점들과 연결되는 대각선을 그릴 수 있습니다. 따라서 한 꼭짓점에서 그릴 수 있는 대각선은 n - 3개입니다.

n개의 꼭짓점이 있으므로 총 대각선 수는 n × (n - 3)이 되지만, 각 대각선은 양쪽 끝 꼭짓점에서 중복으로 계산되기 때문에 최종 공식은 다음과 같습니다.

대각선 개수 = n(n - 3) / 2

C++ 구현 예제

#include<iostream>
using namespace std;

int diagonalCount(int n) {
    return n * (n - 3) / 2;
}

int main() {
    int n = 8;
    cout << n << "변 볼록 다각형의 대각선 개수: " << diagonalCount(n);
    return 0;
}

실행 결과

8변 볼록 다각형의 대각선 개수: 20

복잡도 분석

시간 복잡도: O(1) — 단순한 산술 연산만 수행하므로 입력 크기와 무관하게 일정한 시간이 걸립니다.
공간 복잡도: O(1) — 추가적인 메모리 사용 없이 결과를 계산할 수 있습니다.