[백준/BOJ] 3948번 홍준이의 친위대

https://www.acmicpc.net/problem/3948

3948번: 홍준이의 친위대

 

처음부터 굉장히 디피스러운 문제라고 생각해서 디피 식을 짜는데 3차까지 생각하는 굉장히 극악스러운 방식으로 구현하려고 시도하다 이건 아닌 것 같아 다시 생각해서 1차 디피로 풀게 되었다. 규칙을 찾는 게 중요했는데, 같은 인원수로 작은 키부터 시작했을 때의 가짓 수와 큰 키부터 시작한 가짓수가 같다는 것을 찾는다면 크게 어렵지 않게 풀 수 있는 문제 같다.

 

가장 큰키의 사람이 첫 번째 자리부터 마지막 자리까지 옮겨가며 나올 수 있는 경우의 수를 더하여 해당 인원수에서 구할 수 있는 경우의 수를 구할 수 있었다.

 

 

 

 

 

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<stack>
using namespace std;
unsigned long long dp[25];
unsigned long long con[25][25];
int conbi(int n,int r) {
	if (con[n][r] > 0)return con[n][r];
	if (r == 0||n==r)return con[n][r] = 1;
	unsigned long long num = 1;
	for (int i = n; i >(n-r); i--) {
		num *= i;
	}
	for (int i = 1; i <= r; i++)num /= i;
	return con[n][r] = con[r][n] = num;
}

unsigned long long func(int n) {
	if (n == 1) return dp[1] = 1;
	else if (n == 0)return dp[0] = 1;
	else if (n == 2) {
		dp[2] = 2; return 1;
	}
	else if (dp[n] > 0&&n>1)return dp[n]/2;
	unsigned long long num = 0;
	for (int i = 1; i <= n; i++) {
		num += conbi(n-1,(i - 1))*func(n - i)*func(i-1);
	}
	 dp[n] = num;
	 return dp[n] / 2;
}

int main(void){
	
	int T;
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		int N;
		scanf(" %d", &N);
		if(N>1)printf("%lld\n",func(N)*2);
		else printf("%lld\n", func(N) );

	}
	return 0;
}