-
정상 회담 2 - 1670Algorithm/BOJ 2020. 3. 8. 05:3112345678910111213141516171819202122232425262728293031323334353637383940//1670 - 정상 회담 2#include <iostream>using namespace std;#define MOD 987654321int 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)
'Algorithm > BOJ' 카테고리의 다른 글
공유기 설치 - 2110 (0) 2020.03.10 버블 소트 - 1517 (0) 2020.03.08 배수 공사 (0) 2020.03.07 천재 수학자 성필 - 15815 (0) 2020.03.07 야뱌위 대장 - 15814 (0) 2020.03.07