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

C++로 N개의 교차하지 않는 현(Chord)으로 원을 나누는 방법의 수 구하기

문제 소개

정수 N이 입력으로 주어질 때, 원 위에는 현(chord)의 양 끝이 될 수 있는 2×N개의 점이 존재합니다. 목표는 이 현들을 이용해 원을 나누되, 어떤 두 현도 서로 교차하지 않도록 만드는 경우의 수를 구하는 것입니다.

예를 들어 N=3이라면 원 위의 점은 총 6개가 됩니다. 3개의 현을 그리는 한 가지 방법은 1−2, 3−4, 5−6을 잇는 것입니다.

그 외에 가능한 조합은 다음과 같습니다.

1−6, 2−5, 3−4
1−2, 3−6, 4−5
1−4, 2−3, 5−6
1−6, 2−3, 4−5

따라서 가능한 방법은 모두 5가지입니다.

예제 1

입력

N=4

출력

Count of ways to divide circle using N non-intersecting chords are: 14

설명
현을 그릴 수 있는 점은 총 8개입니다. 첫 번째 현을 하나 그리면, 나머지 점들은 자연스럽게 두 집합으로 나뉩니다. 서로 다른 집합에 속한 점 사이에 현을 그으면 첫 번째 현과 반드시 교차하기 때문에, 각 집합 내부에서만 독립적으로 현을 그어야 합니다.

예제 2

입력

N=6

출력

Count of ways to divide circle using N non-intersecting chords are: 132

설명
현을 그릴 수 있는 점은 총 12개입니다. 마찬가지로 첫 현을 그리는 순간 나머지 점들이 두 집합으로 분리되며, 집합을 가로지르는 현은 허용되지 않습니다.

풀이 접근 방식

이 문제의 답은 수학적으로 잘 알려진 카탈란 수(Catalan Number)와 일치합니다. 핵심 아이디어는 동적 계획법(DP)으로 이전 단계의 계산 결과를 재활용하는 것입니다.

두 점 사이에 임의의 현을 하나 그으면, 남은 점들은 두 개의 집합(set1, set2)으로 나뉩니다. 서로 다른 집합에 속한 점들을 연결하는 현은 첫 번째 현과 교차하므로, 각 집합 내부에서 독립적으로 문제를 해결하면 됩니다. 따라서 전체 경우의 수는 '첫 현 안쪽 영역의 경우의 수 × 바깥쪽 영역의 경우의 수'를 모든 가능한 첫 현에 대해 더한 값이 됩니다.

  • 정수 N을 입력받습니다.
  • divide_circle(int N) 함수는 N개의 교차하지 않는 현으로 원을 나누는 방법의 수를 반환합니다.
  • 전체 점의 개수는 2×N이며, 이를 total_points로 저장합니다.
  • 단계별 경우의 수를 저장할 배열 total_cuts[]를 준비합니다.
  • 점이 0개 또는 2개일 때는 경우의 수가 1이므로 total_cuts[0]과 total_cuts[2]를 1로 초기화합니다.
  • points=4부터 짝수 단위로 순회하며, i개의 점에 대한 총 경우의 수는 j개의 점을 가진 부분 문제와 나머지 i−j−2개의 점을 가진 부분 문제의 곱들의 합입니다.
  • 즉, total_cuts[i] += total_cuts[j] * total_cuts[i−2−j] 점화식을 적용합니다.
  • 반복이 끝나면 total_cuts[total_points]가 곧 전체 방법의 수이므로 이를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int divide_circle(int N){
    int total_points = 2 * N;
    int total_cuts[total_points + 1] = { 0 };
    total_cuts[0] = 1;
    total_cuts[2] = 1;
    for (int i = 4; i <= total_points; i += 2){
        for (int j = 0; j < i-1; j += 2){
            total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j]);
        }
    }
    return total_cuts[total_points];
}
int main(){
    int N = 3;
    cout<<"Count of ways to divide circle using N non-intersecting chords are:"<<divide_circle(N);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of ways to divide circle using N non-intersecting chords are: 5

복잡도 및 참고 사항

이 알고리즘의 시간 복잡도는 O(N²), 공간 복잡도는 O(N)입니다. 참고로 이 문제의 답은 N번째 카탈란 수 CN = (2N)! / ((N+1)!·N!)과 같습니다. 실제로 N=3일 때 5, N=4일 때 14, N=6일 때 132가 출력되는 것을 통해 점화식이 올바르게 작동함을 확인할 수 있습니다.