문제 이해
원형으로 배치된 노드의 개수를 나타내는 숫자 n이 주어진다고 가정해 봅시다. 우리가 구해야 하는 것은 모든 노드가 간선으로 연결되면서, 간선들이 서로 교차하지 않도록 n/2개의 간선을 배치하는 방법의 수입니다. 답이 매우 커질 수 있으므로 최종 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 n = 4라면 출력은 2가 됩니다. 4개의 노드를 서로 교차하지 않게 두 쌍으로 묶는 방식은 정확히 두 가지이기 때문입니다.
접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 하나의 간선을 기준으로 전체 문제를 두 개의 독립적인 하위 문제로 분할하고, 그 결과를 곱하여 누적하는 것입니다.
구체적인 풀이 절차는 다음과 같습니다.
- 크기가 (n/2 + 1)인 dp 배열을 정의합니다.
- dp[0] := 1, dp[1] := 1로 초기화합니다.
- 모듈러 값 m := 10^9 + 7로 설정합니다.
- i := 2부터 n/2까지 반복하면서 다음을 수행합니다.
- high := i로 설정합니다.
- dp[i] := 0으로 초기화합니다.
- j := 1부터 high/2까지 반복하면서 다음을 수행합니다.
- dp[i] := (dp[i] + (2 * dp[j - 1] * dp[high - j])) mod m
- high가 홀수라면 다음을 수행합니다.
- dp[i] := (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) mod m
- dp[i] := dp[i] mod m으로 값을 정규화합니다.
- 최종적으로 dp[n / 2]를 반환합니다.
여기서 인자 2를 곱하는 이유는 간선을 왼쪽에서 오른쪽으로 잇는 경우와 오른쪽에서 왼쪽으로 잇는 경우, 즉 좌우 대칭인 두 가지 배치를 모두 고려하기 위함입니다. 또한 high가 홀수일 때는 중앙에 위치한 간선을 기준으로 양쪽 하위 문제의 크기가 같아지므로, 해당 경우를 별도로 처리해 줍니다.
예제 코드
아래의 C++ 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
vector<long long> dp(n / 2 + 1);
dp[0] = 1;
dp[1] = 1;
int m = 1000000007;
for (int i = 2; i <= n / 2; i++) {
int high = i;
dp[i] = 0;
for (int j = 1; j <= high / 2; j++) {
dp[i] = (dp[i] + (2 * dp[j - 1] * dp[high - j])) % m;
}
if (high % 2) dp[i] = (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) % m;
dp[i] %= m;
}
return dp[n / 2];
}
main(){
int n = 4;
cout << solve(n);
}
입력
4
출력
2
정리
이 알고리즘은 바깥 반복문이 n/2번, 안쪽 반복문이 최대 n/4번 실행되므로 시간 복잡도는 O(n²)이며, dp 배열 하나만 사용하므로 공간 복잡도는 O(n)입니다. 교차하지 않는 매칭(non-crossing matching) 문제는 카탈란 수(Catalan number)와 밀접한 관련이 있는 대표적인 조합론 문제로, 동적 계획법을 익히기에 좋은 예제입니다.