Complete Tree Labeling/하기웅

No older revisions available

풀이 ¶

모든 경우에 답이 다 나오나 결과는 런타임 에러~~(찾을 수 있는 사람 있으면 찾아봐줘~~)

일단 컴플리트 트리의 모든 노드의 개수 = (분기계수^(깊이+1) - 1)/(분기계수-1) 로 구할 수 있다.
예 1)) 분기계수 2에 깊이 2인 컴플리트 트리의 모든 노드의 개수 = (2^(2+1) - 1)/(2-1) = 7개

모든 노드의 개수에서 루트를 제외한 나머지에서 분기의 계수에 맞게 개수를 나누고 그것을 줄세운 것과 같다.
예 2)) 예 1번에 이어서 7개에서 루트 1개를 뺀 3개를 분기계수 2에 맞게 3개씩 3개씩 나눠야 한다.
즉 이것은 combination(루트를 뺀 총 노드 수, 루트를 뺀 총 노드 수/분기계수) 임을 알 수 있다.
combination(6, 6/2)이 되고 이렇게 뽑은 것을 두가지로 세울 수 있으므로 2!의 줄세우는 방법을 곱해준다.
깊이 1에서의 경우의 수 = 분기계수! * combination(루트를 뺀 총 노드수, 루트를 뺸 총 노드수/분기계수)
이 과정 다음에 깊이 2의 트리는 깊이 1의 노드를 루트로 하는 또 다른 하나의 컴플리트 트리로 생각하여 위의 공식을 반복하면 된다.

코드 ¶

~cpp
#include <iostream>
#include <cmath>
#include "BigInteger.h"
using BigMath::BigInteger;

int depth, level, nodeNum, temp, templevel, tempdepth, select, i;

BigInteger labelingNum;

BigInteger factorial[3300];

void InitFactorial()
{
	factorial[1] = 1;
	for(i=2; i<3300; i++)
		factorial[i] = factorial[i-1] * i;
}

BigInteger combination(int a, int b)
{
	if(a==b)
		return 1;
	return factorial[a]/(factorial[b]*factorial[a-b]);
}

BigInteger getCompleteTreeLabeling(int l, int d)
{
	labelingNum=1;
	tempdepth=1;
	if(l==1)
		return 1;
	nodeNum = (pow(l, d+1)-1)/(l-1);
	nodeNum--;
	while(true)
	{
		if(nodeNum==0)
			return labelingNum/l;
		select = nodeNum/l;
		labelingNum = labelingNum * factorial[l] * combination(nodeNum, select);
		nodeNum = select-1;
		tempdepth++;
	}
}

int main()
{
	InitFactorial();
	while(cin>>level>>depth)
		cout << getCompleteTreeLabeling(level, depth) << endl;
	return 0;
}