문제 출처 :
https://www.acmicpc.net/problem/11812
알고리즘 분석 :
문제 해결에 필요한 사항
1. LCA :: http://www.crocus.co.kr/search/lca
2. 완전 K진 트리에 대한 이해
LCA를 복습, 혹은 LCA에 대한 개념을 알기위해 정말 좋은 문제인 것 같다.
일단 이 문제는 N이 10^15까지여서 LCA대로는 풀 수 없다.
우선 이 문제를 풀기 위해서는 완전 K진 트리에 대해 이해를 해야한다.
그래야 각 노드의 부모를 어떻게 찾을 수 있을지도 결정할 수 있고, 각 노드의 레벨을 어떻게 고려해볼지도 결정할 수 있다.
각 노드의 부모를 구하는 법은 아래에도 있지만,
(a + k - 2) / k로 해결 할 수 있다.
이제 각 노드의 레벨을 알아야 하는데 LCA 알고리즘의 원칙대로라면 레벨(Depth)을 이용하여 노드를 같은 높이로 맞추고 해결한다.
하지만 완전 K진 트리를 생각해보면, 노드 번호가 큰 것이 결국 레벨이 크거나 같다.
따라서 레벨을 따지고, 그 노드를 타고 올라가는 과정이 필요가 없어진다.
이 과정이 LCA와 다른 점이지만, LCA를 모른다면 이 문제를 해결 하기에 어려운 부분이다.
따라서 그냥 부모 노드를 찾으면서, 두 노드의 부모 노드가 같아질 때 까지 반복하여 트리를 타고 올라가면 된다.
**
이 문제를 푸는동안 map을 이용하여 level을 다 구한 코드를 만들었는데, 그 방법으로는 WA가 떴다.
아마 pow가 double형이라 정확한 값을 내주지 않아 그런 것 같은데
그 부분을 고치고 레벨을 따라 해결할 수 있는지 코딩하여 올리겠다.(소스 코드 두번째 내용이 map을 이용한 내용)
소스 코드 :
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 | #include <iostream> #include <cstdio> #include <vector> using namespace std; typedef long long ll; ll getParent(long long a, int k) { return (a + k - 2) / k; } int main() { ll n; int k, q; scanf("%lld %d %d", &n, &k, &q); while (q--) { ll left, right; scanf("%lld %lld", &left, &right); if (k == 1) { printf("%lld\n", abs(left - right)); continue; } int len = 0; // left 노드랑 right노드가 다르면 같아질때 까지 조상을 타고 오른다. while (left != right) { while (left > right) { len++; left = getParent(left, k); } while (right > left) { len++; right = getParent(right, k); } } printf("%d\n", len); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
level을 모두 구하여 LCA에 최대한 비슷하게 작성한 코드(WA)
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <iostream> #include <cstdio> #include <vector> #include <cmath> #include <map> using namespace std; typedef long long ll; map<ll, int> m; void makeLevel(int k) { int n = 1; for (ll i = 1; i <= pow(10, 16); i += pow(k, n), n++) m[i] = n; } int getLevel(int n) { auto get = m.lower_bound(n); return get->second; } ll getParent(long long a, int k) { return (a + k - 2) / k; } int main() { ll n; int k, q; scanf("%lld %d %d", &n, &k, &q); if(k != 1) makeLevel(k); while (q--) { ll left, right; scanf("%lld %lld", &left, &right); if (k == 1) { printf("%lld\n", abs(left - right)); continue; } int leftLevel = getLevel(left); int rightLevel = getLevel(right); ll leftPar = getParent(left, k); ll rightPar = getParent(right, k); // 오른쪽이 더 깊게 만들어준다. if (leftLevel > rightLevel) { swap(left, right); swap(leftLevel, rightLevel); swap(leftPar, rightPar); } int len = 0; // left와 right의 높이가 같게 left의 노드가 타고 올라온다. while (leftLevel != rightLevel) { len++; rightLevel--; right = getParent(right, k); } // left 노드랑 right노드가 다르면 같아질때 까지 조상을 타고 오른다. if (left != right) { while (left != right) { len += 2; leftLevel--; rightLevel--; left = getParent(left, k); right = getParent(right, k); } } printf("%d\n", len); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[2573번] 빙산 (0) | 2017.04.14 |
---|---|
[1600번] 말이 되고픈 원숭이 (0) | 2017.04.14 |
[5639번] 이진 검색 트리 (0) | 2017.04.13 |
[2240번] 자두 나무 (2) | 2017.04.13 |
[3048번] 개미 (0) | 2017.04.13 |