문제 정의


 - 여러 소국가 대표 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]

를 모두 더하면 된다.




소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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;
}
cs


'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 1194 달이 차오른다, 가자.  (0) 2020.08.11
BOJ 6087 레이저통신  (0) 2020.08.09
BOJ 11505 구간 곱 구하기  (0) 2020.08.06
1344 축구  (0) 2018.06.01
1351 무한 수열  (0) 2018.05.28

+ Recent posts