1670 정상 회담 2

문제 정의

 - 여러 소국가 대표 N명이 원탁에 모여있고, 자리는 정해져있다. (N<=10000, 짝수)

 - '완벽한 악수'는 N명이 모두 빠지지 않고 악수하며, 손이 교차하지 않는 악수를 하는 경우이다.

 - 완벽한 악수의 경우의 수를 987654321로 나눈 나머지를 구한다.

N=4 의 경우, 값은 2이다. 마지막 x로 교차하는 경우는 완벽한 악수가 아니다.

---

문제 풀이

이 문제는 DP로 풀 수 있다. 한명의 대표를 기준으로 분할해 볼 수 있다.

N=8인 경우

       1     2

8                   3

7                   4

       6     5

일때, 대표 1번을 기준으로 

 1.  2번과 악수하는 경우 D[0]*D[6]

 2.  4번과 악수하는 경우 D[2]*D[4]

 3.  6번과 악수하는 경우 D[4]*D[2]

 4.  8번과 악수하는 경우 D[6]*D[0]

를 모두 더하면 된다.

---

소스코드

#include<stdio.h>
long dp[10002];
const long MOD = 987654321;
int main() {
    int n;
    scanf("%d", &n);
    dp[0] = dp[2] = 1;
    for (int i = 4; i <= n; i+=2) {
        for (int j = 0; j <= i-2; j += 2) {
            dp[i] += dp[j] * dp[i - j - 2];
            dp[i] %= MOD;
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}