반응형

문제 출처 :


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(1016); 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