C++로 n개 원의 최대 교점 개수 구하기

문제 개요

이 튜토리얼에서는 n개의 원이 가질 수 있는 최대 교점 개수를 구하는 프로그램을 다룹니다.

원의 개수 n이 주어졌을 때, 이 원들이 서로 만들 수 있는 최대 교점의 수를 계산하는 것이 목표입니다.

접근 방법

두 원은 최대 2개의 교점을 가질 수 있습니다. 따라서 n개의 원에서 가능한 모든 원의 쌍(pair)마다 최대 2개씩의 교점이 발생합니다.

n개의 원으로 만들 수 있는 쌍의 개수는 조합 공식 C(n, 2) = n(n-1)/2이므로, 최대 교점의 수는 다음과 같이 계산됩니다.

최대 교점 수 = 2 × C(n, 2) = n × (n - 1)

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 최대 교점 개수를 반환하는 함수
int intersection(int n) {
    return n * (n - 1);
}
int main() {
    cout << intersection(3) << endl;
    return 0;
}

출력 결과

6

동작 설명

원이 3개인 경우, 가능한 원의 쌍은 (1,2), (1,3), (2,3)으로 총 3가지입니다. 각 쌍은 최대 2개의 교점을 가질 수 있으므로, 전체 교점 수는 3 × 2 = 6개가 됩니다. 이는 공식 n(n-1) = 3 × 2 = 6과 정확히 일치하며, 시간 복잡도는 O(1)로 매우 효율적입니다.