[c++]백준 3038 - 완전 이진 트리

0. [c++] 백준  -

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

1. 풀이

BaaaaaaaaaaaarkingDog님이 올려주신 풀이 참고해서 풀었습니다.

https://blog.encrypted.gg/448

이 문제에서 핵심은 좌 우 밸런스를 맞춰주는 것인데, 그 밸런스를 맞춰주기 위해서 leaf 부분의 개수가 branch 부분보다 1이 더 큰 부분을 활용한다.

항상 1을 루트로 고정하고, N레벨의 트리는 N-1레벨의 트리를 2번 복제하여 만들어준다.

이때, 복제의 기본은 2를 곱해주어서 만드는 것이 기본인데, 한 쪽은 leaf 부분은 1을 더해주고,  다른 쪽은 branch 부분에 1을 더해줌으로써 1의 차이를 유지시켜주는 키가 된다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include<iostream> #include<vector>   using namespace std;   vector<int> arr[16]; vector<int> depth[16];   void preCalc() {     arr[1].push_back(1);     depth[1].push_back(1);     for (int i = 2; i <= 15; i++) {         arr[i].resize((1 << i) - 1);         arr[i][0] = 1;         depth[i].resize((1 << i) - 1);         depth[i][0] = 1;         for (int j = 1; j < (1 << (i - 1)); j++) {             depth[i][j] = depth[i - 1][j - 1] + 1;             depth[i][(1<<(i - 1)) + j - 1] = depth[i - 1][j - 1] + 1;             if (depth[i][j] != i) {                 arr[i][j] = arr[i - 1][j - 1] * 2 + 1;                 arr[i][(1 << (i - 1)) + j - 1] = arr[i - 1][j - 1] * 2;             }             else {                 arr[i][j] = arr[i - 1][j - 1] * 2;                 arr[i][(1 << (i - 1)) + j - 1] = arr[i - 1][j - 1] * 2 + 1;             }         }     }     }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     int N;     cin >> N;       preCalc();       for (int i = 0; i < (1 << N) - 1; i++) {         cout << arr[N][i] << " ";     }         return 0; } Colored by Color Scripter

cs

3. 참고

https://blog.encrypted.gg/448

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!