백준 9934 _ 완전 이진 트리

www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

---

✨ 내 소스 코드

#include<iostream>
#include <vector>
#include <math.h>
using namespace std;
int tree[10][2048];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int K;
	cin >> K;
	int level = K;
	vector<int> vec;
	for (int i = 0; i < pow(2, K) -1; i++) {
		int temp;
		cin >> temp;
		vec.push_back(temp);
	}

	int j = 0;
	int x = 2;
	int t = 0;
	tree[0][0] = vec[pow(2, K) / 2 - 1];

	while (K--) {
		for (int i = 0; i < pow(2,K); i++) {
			tree[K][j] = vec[i * x + t];
			j++;
		}
		x *= 2;
		j = 0;
		t = (t + 1) * 2 - 1;
	}
	
	cout << tree[0][0] << endl;	
	for (int i = 1; i <= level; i++) {
		for (int j = 0; tree[i][j] != 0; j++) {
			cout << tree[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}

 

🙏 문제 풀이

K가 4인 트리는 위와 같이 이루어지게 된다. 숫자는 각 노드가 가지게 될 값을 가지고 있는 배열의 index를 의미한다.

 

level 3의 경우만 놓고 보면, 0 2 4 6 8 10 12 14 와 같이 '2씩 증가'한다는 일정한 규칙으로 진행이 된다.

level 2의 경우도 1 4 9 13 으로 진행되며 값이 '4씩 증가'하는 것을 확인 할 수 있다

level 1의 경우로 3 11로 값이 '8씩 증가'하는 것을 볼 수 있다

 

그렇다면 level 3은 2씩 증가, level 2는 4씩 증가, level 1은 8씩 증가이니, 증가하는 값에도 2제곱이라는 규칙이 있음을 알 수 있다.

 

각 레벨에서 가장 처음 시작하는 값인 0 ,1, 3의 경우도 보면

(레벨+1)*2-1 이라는 값이라는 것을 확인 할 수 있다.

 

 

⭐ 문제 풀이 결과