[코드포스 Round 677] E. Two Round Dances

 

 

 

음.. 뭔가.. 수학... 모르겠... 해서 패스했던 문제

 

그래서 풀이 들으면서 풀었다. 아ㅋㅋㅋㅋ 그리고 two round dance 저 round가 둥글게란 뜻이였다. 나는 두 개로 나누니깐 그 경기할 때 라운드 그런거 생각했었음. 1라운드에 춤 추는 사람 2라운드에 춤 추는 사람. 

 

Round dance is a dance circle consisting of 1 or more people

 

여기서 확실히 얘기해주는데 넘겼구나

 

암튼 풀이는 이렇다

 

(k-1)! * (k-1) ! * C(n, k) / 2 (k = n / 2)

 

 

일단 그룹에 속하는 사람 뽑는 경우가 n명 중  n / 2명 뽑는 거니깐 C(n, n/2)이고 두 그룹의 순서는 상관 없어서 / 2한다

 

다음으로 원으로 도는 순서 구해야 하는데 이건 원순열로 구할 수 있다. 원순열은 (n - 1)!이다.

 

(n/2 - 1)! * (n/2 - 1) ! * C(n, n/2) / 2 그래서 이렇게 식이 만들어진다. 

 

아 원순열은 일렬로 있는 순열이 아니라 원형으로 생긴 순열인데 빙글 돌려도 똑같다는 게 다르다.

 

그래서 일렬로 나열하면 n!인데 빙글 돌려도 같은 경우니깐 같은 경우의 수가 n개가 생김

 

그래서 n! / n = (n-1)!된다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

i64		C(i64 n, i64 r)
{
	if (r == n || r == 0)
		return 1;
	return C(n - 1, r - 1) + C(n - 1, r);
}

i64		pac(i64 n)
{
	if (n == 1 || n == 0)
		return 1;
	return n * pac(n - 1);
}

int     main()
{
	i64 n;
	scanf("%lld", &n);

	i64 k = n / 2;
	printf("%lld\n", pac(k - 1) * pac(k - 1) * C(n, k) / 2);

	return 0;
}

 

다음 목표 : 조합론 공부하기