[c++] 백준 9934, 완전 이진 트리

백준 9934

🌲 문제 요약

상근이가 종이에 적은 빌딩 방문 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 문제.

🌲 문제 풀이

주어진 순서의 중간에 있는 빌딩 번호가 각 레벨의 가장 앞에 온다는 규칙을 이용하여 문제를 해결한다.
solve 함수는 시작 위치 s와 끝 위치 e를 인자로 받아, 가운데 위치 mid를 계산하여 다음의 연산을 수행한다.
벡터 ret의 해당 idx 위치에 a[mid]를 push_back하고, mid를 기준으로 나누어진 두 구역에 대하여 다시 한번 solve 함수를 호출한다.
solve 함수는 s와 e가 같은 값을 가지는 경우 ret의 해당 idx 위치에 a[s]를 push_back하고 return한다.

🌲 주의

solve 함수를 호출하는 과정에서 만약 s가 e보다 큰 값을 가진다면 return하도록 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int k, n, a[1030];
vector<int> ret[15];

void solve(int s, int e, int idx) {
	if (s > e) return;
	if (s == e) {
		ret[idx].push_back(a[s]);
		return;
	}
	int mid = (s + e) / 2;
	ret[idx].push_back(a[mid]);
	solve(s, mid - 1, idx + 1);
	solve(mid + 1, e, idx + 1);
	return;
}

int main() {
	cin >> k;
	n = pow(2, k) - 1;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	solve(0, n - 1, 1);
	
	for (int i = 1; i <= k; i++) {
		for (int x : ret[i]) {
			cout << x << ' ';
		}
		cout << '\n';
	}
	
	return 0;
}