Algorithm/BOJ
정상 회담 2 - 1670
jhg0406
2020. 3. 8. 05:31
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
//1670 - 정상 회담 2
#include <iostream>
using namespace std;
#define MOD 987654321
int N;
long long cache[10001];
void init()
{
cin >> N;
for(int i = 0; i<=10000; ++i)
cache[i] = -1;
for(int i = 1; i<=10000; i += 2)
cache[i] = 0;
cache[0] = cache[2] = 1;
cache[4] = 2;
}
long long dp(int num)
{
long long& ret = cache[num];
if(ret != -1)
return ret;
ret = 0;
int t = num -2;
for(int i = 0; i<t/2; i += 2)
ret += ((2*dp(i))%MOD)*dp(t-i)%MOD;
ret += (dp(t/2)*dp(t/2));
ret %= MOD;
return ret;
}
int main()
{
init();
cout << dp(N);
}
|
cs |
https://www.acmicpc.net/problem/1670
1670번: 정상 회담 2
첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다.
www.acmicpc.net
정상 회담 2
dp문제 입니다.
n명이 원탁에 있을 때, 기준 한명과 나머지 사람들이 악수하는 n-1의 경우로 나눌수 있습니다.
각각의 경우에 대해, 기준과 악수하는 사람을 경계로 2가지 부분문제를 만들수 있고, 부분문제의 곱을 구해 모든 경우에 대해 더하게 되면, n명이 원탁에 있을 때 겹치지 않게 악수나는 경우의수 입니다.
C(n) : n명이 안겹치게 악수할수 있는 경우의 수
C(n) = (0<= k < (n-2)/2)[2*C(k)*C(n-2-k)] + C((n-2)/2)*C((n-2)/2)
