문제 소개
짝수 명의 사람 n명이 원을 따라 둘러 서 있다고 가정해 봅시다. 각 사람은 자신을 제외한 다른 한 사람과 악수를 하므로, 전체 악수 횟수는 항상 n / 2번이 됩니다. 우리가 구해야 할 것은 이렇게 진행되는 모든 악수 중에서 서로 교차(엇갈림)하지 않는 경우의 수입니다.
단, 가능한 방법의 수가 매우 커질 수 있기 때문에 최종 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 n = 2라면, 두 사람이 서로 악수하는 방법은 단 하나뿐이므로 출력은 1입니다.
문제의 본질: 카탈란 수(Catalan Number)
흥미롭게도 이 문제는 조합론에서 잘 알려진 카탈란 수(Catalan Number)와 정확히 일치합니다. n명의 사람이 원 위에서 교차하지 않고 악수하는 방법의 수는 C(n/2), 즉 n/2번째 카탈란 수와 같습니다. 원 위의 한 사람을 기준으로 잡으면, 그 사람의 상대는 원을 두 부분으로 나누게 되고, 각 부분 내부의 악수들은 독립적으로 계산할 수 있기 때문입니다. 이 성질을 활용하면 동적 계획법(DP)으로 깔끔하게 해결할 수 있습니다.
풀이 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
모듈로 값
m := 10^9 + 7을 정의합니다.크기가
(n+1)인 배열dp를 선언합니다.기저 조건으로
dp[0] := 1을 설정합니다. (아무도 없을 때의 경우의 수)i를 0부터 n까지 2씩 증가시키며 반복합니다:
j를 0부터 i-2까지 2씩 증가시키며 반복합니다:
dp[i] := dp[i] + (dp[j] mod m * dp[i - 2 - j] mod m)dp[i] := dp[i] mod m으로 나머지를 유지합니다.
최종적으로
dp[n] mod m을 반환합니다.
여기서 dp[j]는 첫 번째 사람의 악수로 분리된 한쪽 영역의 경우의 수, dp[i-2-j]는 반대편 영역의 경우의 수를 의미합니다. 두 값을 곱하고 모두 더하는 과정이 카탈란 수의 점화식과 동일한 구조입니다.
예시 구현
아래 코드를 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9+7;
typedef long long int lli;
class Solution {
public:
int numberOfWays(int n) {
vector <lli> dp(n+1);
dp[0] = 1;
for(int i = 0; i <= n; i+=2 ){
for(int j =0 ; j <= i-2; j+=2){
dp[i] += (dp[j]%m * dp[i-2-j]%m)%m;
dp[i]%=m;
}
}
return dp[n]%m;
}
};
main(){
Solution ob;
cout << (ob.numberOfWays(2));
}입력
2
출력
1
마치며
이 문제의 시간 복잡도는 O(n²)이며, 공간 복잡도는 O(n)입니다. 원 위의 대칭성과 카탈란 수의 점화식을 결합하면 교차하지 않는 매칭 문제를 효율적으로 해결할 수 있다는 점이 핵심 포인트입니다. 비슷한 패턴은 괄호 생성, 다각형 삼각분할 등 다양한 조합론 문제에도 응용되므로 함께 익혀두면 큰 도움이 됩니다.