악수 문제(카달란 수)

문제

n명의 회사원이 둥근 테이블에 앉아 회의를 하려고 한다. 회의를 시작하기 전에 그들은 먼저 악수를 해야한다.  회사원들은 각각 다른 사람과 악수를 해야 하며 모든 악수는 동시에 진행되어야 하지만 서로의 팔이 교차되어서는 안 된다. 정수가 주어졌을 때 그만큼의 직장인이 하는 악수가 성립하는 조합의 수를 리턴하는 함수를 작성하라.

입출력 예시

입력 1)

int n = 2

출력 1)

1

입력 2)

int n = 8

출력 2)

14

풀이

이 문제를 풀기 위해서는 카달랑 수의 개념을 알아야 한다. 조합론에서, 카탈란 수(Catalan數, 영어: Catalan number)는 이진 트리의 수 따위를 셀 때 등장하는 수열이다. 위 문제를 통해 수열의 점화식을 알아보자.

모든 사람이 악수를 해야 하기 때문에 주어지는 정수는 항상 짝수이다. 이를 전제로 각 사람수에 대해 악수가 성립하는 경우의 수를 살펴보면 다음과 같다.

	사람 수	악수가 성립하는 경우의 수
C1	2	1
C2	4	2 = C1 + C1 // 2명씩 나누어 생각하면 C1이 두개 있는 것과 같다.
C3	6	5 = C2 + C1*C1 + C2       // 인접한 2명이 악수하는 경우 남은 사람의 경우의 수는 C2와 같다.                                      // 떨어진 2명이 악수하는 경우 남은 사람은 각각 C1과 같은 경우의 수를 가지므로 C1*C1
C4	8	14 = C3 + C1*C2 + C2*C1 + C3 // 인접한 2명이 악수하는 경우 나머지 사람 6명의 경우의 수는 C3와 같다. 이 사건은 두 번 발생한다. // 2명 떨어진 두 사람이 악수하는 경우에는 한쪽은 C1, 반대쪽은 C2이다. 이런 경우는 두번 발생한다.
C5	10	42 = C4 + C1*C3 + C2*C2 + C3*C1 + C4 // 인접한 2명이 악수하는 경우 나머지 8명의 경우의 수는 C4와 같다. 이 사건은 두 번 발생한다. // 2명 떨어진 두 사람이 악수하는 경우에는 한쪽은 C1, 반대편은 C3의 경우가 발생한다. 두 번 발생한다. // 4명 떨어진 두 사람이 악수하는 경우에는 양쪽에서 C2 와 같은 경우의 수가 생긴다.
Cn	n * 2	Cn = Cn-1 + C1*Cn-2 + C2*Cn-3 + ... + Cn-3*C2 + Cn-2*C1 + Cn-1

위를 일반화 하면 Cn=C0⋅Cn−1+C1⋅Cn−2+C2⋅Cn−3+⋯+Cn−2⋅C1+Cn−1⋅C0 가 된다. 이 일반식을 코드에 적용하면 문제를 간단하게 풀 수 있다.

코드

public long countPerfect(int n) {
    
    long[] dp = new long[n/2];
    
    dp[0] = 1;
    for (int i = 1; i < n/2; i++) {
        dp[i] = 0;
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j]*dp[i-j-1];
        }
    }
    
    return dp[n/2];
}