Aproximate Binary Tree/김상섭

No older revisions available

~cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <math.h>
using namespace std;

typedef struct data * data_pointer;
struct data
{
	string name;
	int value;
	vector<data> nodes;
	data_pointer left_child, right_child;	
};

bool comapare(data & a, data & b)
{
	return a.name < b.name;
}

void init(data_pointer dp)
{
	dp->left_child = dp->right_child = NULL;
}

void createABT(data_pointer dp)
{
	if(dp)
	{
		
		int left_sum = 0, right_sum= 0, min_index = 0;
		double min_total_weight_sum, temp;
		for(int i = 1; i < dp->nodes.size(); i++)
		{
			right_sum +=dp->nodes[i].value;
		}
		
		min_total_weight_sum = right_sum*sqrt(dp->nodes.size()-1);
		for(i = 1; i < dp->nodes.size(); i++)
		{
			left_sum += dp->nodes[i-1].value;
			right_sum -= dp->nodes[i].value;
			temp = left_sum*sqrt(i-1) + right_sum*sqrt(dp->nodes.size() - i - 1);
			if(temp < min_total_weight_sum)
			{
				min_total_weight_sum = temp;
				min_index = i;
			}		
		}
		dp->name = dp->nodes[min_index].name;
		dp->value = dp->nodes[min_index].value;	
		// 왼쪽 자식이 있을때
		if(min_index != 0)
		{
			dp->left_child = new data;
			init(dp->left_child);
			for(int i = 0; i < min_index; i++)
				dp->left_child->nodes.push_back(dp->nodes[i]);
			createABT(dp->left_child);
		}
		
		// 오른쪽 자식이 있을때
		if(min_index != dp->nodes.size()-1)
		{
			dp->right_child = new data;
			init(dp->right_child);
			for(int i = min_index +1; i < dp->nodes.size(); i++)
				dp->right_child->nodes.push_back(dp->nodes[i]);
			createABT(dp->right_child);
		}	
		dp->nodes.clear();
	}
}

void show(data_pointer dp)
{
	if(dp)
	{
		show(dp->left_child);
		cout << dp->name << " ";
		show(dp->right_child);
	}
}

int cost(data_pointer dp, int level)
{
	if(dp)
	{
		return cost(dp->left_child, level + 1) + cost(dp->right_child, level + 1) + dp->value * level;
	}
	return 0;
}

int main()
{
	int nodeNum, value;
	data temp;
	string name;
	data_pointer root = new data;
	init(root);
	cin >> nodeNum;
	for(int i = 0; i < nodeNum; i++)
	{
		cin >> name >> value;
		temp.name = name;
		temp.value = value;
		root->nodes.push_back(temp);
	}
	sort(root->nodes.begin(),root->nodes.end(),comapare);
	createABT(root);
	show(root);
	cout << endl;
	cout << cost(root,1) << endl;
	return 0;
}