Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀기: 총 n개의 점 중 m개가 일직선상에 있을 때 만들 수 있는 삼각형의 개수

문제 정의

2차원 평면 위의 점들을 나타내는 두 변수 n과 m이 주어진다고 가정해 봅시다. 전체 n개의 점 중 m개의 점은 한 직선 위에 놓여 있습니다. 우리의 목표는 이 n개의 점을 이용해 만들 수 있는 삼각형의 개수를 구하는 것입니다.

일직선상의 점(Collinear Points)이란 같은 직선 위에 위치한 점들을 의미합니다. 아래 그림에서 점 A와 B는 서로 일직선상에 있습니다.

C++로 풀기: 총 n개의 점 중 m개가 일직선상에 있을 때 만들 수 있는 삼각형의 개수

접근 방식: 조합 공식 활용

n=4(점 A, B, C, D), m=2(점 A, B)인 경우를 예로 들어 살펴보겠습니다.

  • 4개의 점 중 임의로 3개를 선택하는 경우의 수 = 4C3
  • 단, 일직선상의 점들은 삼각형을 형성할 수 없으므로 앞서 계산한 경우의 수에서 제외해야 함 = 2C3
  • 따라서 총 삼각형의 수 = 4C3 − 2C3 = 4 − 0 = 4 (ABC, ACD, BCD, ABD)

일반화하면, n과 m이 주어졌을 때 만들 수 있는 삼각형의 개수는 nC3 − mC3 공식으로 구할 수 있습니다.

예제

예제 1

입력 − n=5, m=3

출력 − 총 n개의 점 중 m개가 일직선상에 있을 때 만들 수 있는 삼각형의 개수 − 9

설명 − 총 삼각형 수 = 5C3 − 3C3 = 10 − 1 = 9

예제 2

입력 − n=10, m=5

출력 − 총 n개의 점 중 m개가 일직선상에 있을 때 만들 수 있는 삼각형의 개수 − 110

설명 − 총 삼각형 수 = 10C3 − 5C3 = 120 − 10 = 110

프로그램에서 사용된 알고리즘

조합(combination) 값을 계산하기 위해 파스칼 삼각형(Pascal Triangle)을 활용합니다. 파스칼 삼각형의 각 행은 이전 행의 값들을 더하는 방식으로 채워지며, 이를 통해 nCr 값을 효율적으로 구할 수 있습니다.

  • 점의 개수를 나타내는 변수 n과 m을 입력받습니다.
  • 함수 collinear_points(int n, int m)는 n과 m을 인자로 받아 총 n개의 점 중 m개가 일직선상에 있을 때 만들 수 있는 삼각형의 개수를 반환합니다.
  • count = check(n, 3) − check(m, 3)으로 설정합니다. (nC3 − mC3 계산)
  • 함수 check(int n, int r)는 n과 r을 받아 nCr 값을 반환합니다.
  • 길이가 r+1인 배열 arr를 선언합니다.
  • memset을 사용하여 배열 전체를 0으로 초기화합니다.
  • arr[0] = 1로 설정합니다.
  • i=1부터 i≤n까지, 그리고 j=min(i, r)부터 j>0까지 두 개의 for 루프를 돌며 arr[j] = arr[j] + arr[j-1] 연산으로 파스칼 삼각형을 채워 나갑니다.
  • 최종적으로 arr[r]이 nCr 값이 되며, 이를 반환합니다.
  • check() 함수 호출이 완료되면 삼각형의 개수를 얻을 수 있습니다.
  • count를 결과값으로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int check(int n, int r){
    int arr[r+1];
    memset(arr, 0, sizeof(arr));
    arr[0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = min(i, r); j > 0; j--){
            arr[j] = arr[j] + arr[j-1];
        }
    }
    return arr[r];
}
int collinear_points(int n,int m){
    int count = check(n, 3) - check(m, 3);
    return count;
}
int main(){
    int n = 6, m = 2;
    cout<<"Count of triangles with total n points with m collinear are: "<< collinear_points(n, m);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of triangles with total n points with m collinear are: 20

마무리

이 알고리즘은 팩토리얼을 직접 곱하는 대신 파스칼 삼각형을 덧셈 기반의 동적 프로그래밍 방식으로 채워 나가기 때문에, 중간 계산 과정에서 값이 지나치게 커지는 오버플로우 위험을 줄일 수 있습니다. 또한 시간 복잡도는 O(n × r)로, 점의 개수가 많아져도 안정적으로 조합 값을 계산할 수 있다는 장점이 있습니다.