[백준/BOJ] 백준 12767번 : Ceiling Function

www.acmicpc.net/problem/12767

12767번: Ceiling Function

트리의 모양을 저장하기 위해 트리에 숫자가 들어간 위치를 this_check에 저장했다. 위치는 부모 노드의 왼쪽은 (부모 노드 위치번호*2)+1을 하고, 부모 노드의 오른쪽은 (부모 노드 위치번호*2)+2를 해서 나타냈다. (루트의 위치번호는 0) 또한 주의해야 될 점은 Make_tree(node*& here, int check_number, int insert_number) 처럼 구조체 포인터도 원본 전달하려면 &붙인다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
using namespace std;

set<vector<int>> check;
int n, k;
vector<int> this_check;

struct node {
	int number;
	node* left_child;
	node* right_child;
};

node* Make_node()
{
	node* ret = new node();

	ret->left_child = NULL;
	ret->right_child = NULL;

	return ret;
}

void Delete_node(node*& here)
{
	if (here == NULL)
		return;

	Delete_node(here->left_child);
	Delete_node(here->right_child);

	delete(here);
}

//구조체 포인터도 원본 전달하려면 &붙인다
void Make_tree(node*& here, int check_number, int insert_number)
{
	if (here == NULL)
	{
		here = Make_node();
		here->number = insert_number;

		//수가 들어간 위치를 저장한다
		this_check.push_back(check_number);

		return;
	}

	//넣는 수가 현재 위치 수 보다 작을때
	if (here->number > insert_number)
	{
		Make_tree(here->left_child, (check_number * 2) + 1, insert_number);
	}

	//넣는 수가 현재 위치 수 보다 클때
	else if (here->number < insert_number)
	{
		Make_tree(here->right_child, (check_number * 2) + 2, insert_number);
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		node* tree = new node();
		tree = NULL;
		this_check.clear();

		for (int j = 0; j < k; j++)
		{
			int input;
			cin >> input;

			Make_tree(tree, 0, input);
		}

		sort(this_check.begin(), this_check.end());
		check.insert(this_check);

		Delete_node(tree);
	}

	cout << check.size();

	return 0;
}