백준 9934 C++

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

9934번: 완전 이진 트리

되게 이상한 규칙을 찾아서 재귀로 풀려고 했는데 틀렸다.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;



/*처음에 상근이는 트리의 루트에 있다.
  왼쪽을 먼저 방문한다.
  그 다음 중앙 방문
  오른쪽 방문
  위로 이동
*/

int k; // 1<= k <= 10;		k = 10일 때 전체 노드 수  = 1024 -> 배열을 전체로 잡으면 1050으로 잡으면 될듯
int nodeCount;
vector<int> treeNode;
vector<int> tree[14];

void go(int size, int level)
{
	if (level == 0) {
		//cout << "push back level : " << level << "  index:" << size / 2 << "   r:" << treeNode[size / 2] <<"\n";
		tree[level].push_back(treeNode[size / 2]);		//절반에 들어있는 수가 루트의 수가 된다. -> 1레벨에 루트노드를 넣어준다.
		go(size - (size / 2 + 1), level + 1);
		return;
	}
	else if (level == k - 1) {		//리프노드까지 왔다
		//지금 들어온 size index의 양 옆
		//cout << "push back level : " << level << "  index:" << size / 2 << "   r:" << treeNode[size -1] << " & " << treeNode[size + 1] << "\n";
		tree[level].push_back(treeNode[size - 1]);
		tree[level].push_back(treeNode[size + 1]);
		return;
	}

	//level이 0이 아니라면
	for (int i = 0; i < level; i++) {
		tree[level].push_back(treeNode[size - (size / 2) - 1]);
		tree[level].push_back(treeNode[size + (size / 2) + 1]);

		go(size - (size / 2) - 1, level + 1);
		go(size + (size / 2) + 1, level + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> k;
	//cout << pow(2, k);
	nodeCount = pow(2, k) - 1;

	for (int i = 0; i < nodeCount; i++) {
		int t; cin >> t;
		treeNode.push_back(t);
	}

	go(nodeCount, 0);

	for (int i = 0; i < 10; i++) {
		if (tree[i].size() == 0) continue;

		for (int j = 0; j < tree[i].size(); j++) {
			//cout << "i: " << i << "   j: " << j << "\n";
			cout << tree[i][j] << " ";
		}

		cout << "\n";
	}

}

그래도 정답을 보니 아이디어는 맞았던게 절반을 잘라서 계속 나아간다는 것은 맞았다.

내가 생각하지 못한 점은 배열을 잘라서 재귀를 돌리면 된다는 것이었다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int k;
int a[1030];
vector<vector<int>> tree(10);

void go(int s, int e, int level)
{
	if (s > e) return;
	if (s == e) {
		tree[level].push_back(a[s]);
		return;
	}

	tree[level].push_back(a[(s+e) / 2]);
	//cout << "push back num : " << a[ (s + e) / 2] << "    level : " << level << " \n";
	go(s, (s + e) / 2 - 1, level + 1);
	go((s + e) / 2 + 1, e, level + 1);
	
	return;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> k;
	int nodeCount = pow(2, k) - 1;
	for (int i = 0; i < nodeCount; i++)
	{
		int t; cin >> t;
		a[i] = t;
	}

	//cout << "node COunt : " << nodeCount << " \n";
	go(0, nodeCount - 1, 0);

	//cout << " OVER";

	for (int i = 0; i < tree.size(); i++) {
		if (tree[i].size() == 0) continue;
		for (int j = 0; j < tree[i].size(); j++) {
			cout << tree[i][j] << " ";
		}
		cout << "\n";
	}
}