C++로 n개의 직선이 만들 수 있는 최대 교차점 개수 구하기

이 튜토리얼에서는 n개의 직선이 만들 수 있는 최대 교차점 개수를 구하는 프로그램을 살펴보겠습니다.

직선의 개수 n이 주어졌을 때, 이 직선들이 형성할 수 있는 최대 교차점의 개수를 계산하는 것이 목표입니다.

접근 방식과 핵심 원리

교차점의 개수가 최대가 되려면 다음 조건을 만족해야 합니다.

- 어떤 두 직선도 서로 평행하지 않아야 합니다.
- 세 개 이상의 직선이 한 점에서 동시에 만나서는 안 됩니다.

위 조건이 충족되면 모든 직선 쌍이 서로 다른 점에서 정확히 한 번씩 교차하므로, 가능한 모든 직선 쌍의 개수가 곧 최대 교차점 개수가 됩니다. 이는 조합 공식으로 표현할 수 있으며, n개 중 2개를 선택하는 경우의 수인 nC2 = n(n-1)/2와 같습니다.

예시 코드

#include <bits/stdc++.h>
using namespace std;
#define ll long int
// 최대 교차점 개수를 구하는 함수
ll countMaxIntersect(ll n) {
    return (n) * (n - 1) / 2;
}
int main() {
    ll n = 8;
    cout << countMaxIntersect(n) << endl;
    return 0;
}

출력 결과

28

직선이 8개인 경우, 8 × 7 ÷ 2 = 28개의 교차점이 만들어질 수 있습니다. 이처럼 반복문 없이 단순한 수학 공식만으로도 O(1) 시간 복잡도에 문제를 해결할 수 있어 매우 효율적입니다.