반응형
문제 출처 :
https://www.acmicpc.net/problem/9934
알고리즘 분석 :
문제 해결에 필요한 사항
1. 완전 이진 트리 이해
2. 완전 이진 트리의 구성
3. 중위 순회
예제 입력 자체가 현재 중위 순회로 되어있다.
이 입력을 잘 살펴보면 트리를 만들 필요가 없이 트리가 어떻게 생긴지 판별 할 수 있게 된다.
5
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
이 수를 예제로 본다면
이렇게 구성되어 있다는 것을 확인 할 수 있다.
즉, 규칙성을 찾으면 문제를 해결 할 수 있다.
루트에 있는 값은 (입력받은 수 / 2) - 1 // 배열이기에 - 1 임을 알 수 있고
아래로 내려갈수록 노드의 시작 위치가 0 1 2 4 8 16 ..
그다음 노드 위치가 *2 *4 *8 *16.. 순으로 되어있다는 것을 알 수 있다.
소스 코드 :
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 49 50 51 52 53 54 55 56 57 58 59 60 | #include <iostream> #include <math.h> using namespace std; int tree[11][2048]; int arr[2048]; int main() { int level, tmp; int i = 2; int t = 0; int j = 0; cin >> level; tmp = level; for (int k = 0; k < pow(2, level) - 1; k++) cin >> arr[k]; // level :: 3이라 가정하면 while (level--) { // level :: 2 if (level <= 0) break; for (int n = 0; n < pow(2, level); n++) { tree[level][j] = arr[n * i + t]; j++; } i *= 2; t = (t+1)*2 - 1; j = 0; } tree[level][0] = arr[(int)pow(2, tmp) / 2 - 1]; // level :: 0 cout << tree[level][0] << endl; // while문에선 level이 1부터 시작 while(level++ != tmp) { for (int n = 0; tree[level][n] != 0; n++) cout << tree[level][n] << " "; if(level != tmp) cout << endl; } } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[10824번] 네 수 (0) | 2016.11.03 |
---|---|
[13420번] 사칙연산 (0) | 2016.11.03 |
[2075번] N번째 큰 수 (0) | 2016.11.03 |
[2188번] 축사 배정 (5) | 2016.11.02 |
[1786번] 찾기 (KMP Algorithm) (0) | 2016.11.02 |