티스토리 뷰

알고리즘 관련/BOJ

BOJ)13505 두수 XOR

JASON 자손9319 2017. 1. 5. 21:25

문제: icpc.me/13505


N개의 수 중에서 두 수를 정해 XOR한 값이 가장 크게 하는 문제이다.


두수가 XOR을 하여 가장 큰 수가 되려면 서로 다른 비트가 가장 많아야 할 것이다.


트라이를 이용하여 모든 수를 비트 순서대로 저장 한 후 이후 모든 수에 대해서 자기와 다른 비트를 따라가도록 하면 된다.


이때 가장 큰 수가 되야 하므로 비트는 높은 자리 수 부터 검사한다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, t, res;
int arr[100010];
char c[33];
struct Trie {
    Trie* go[2];
    Trie() {
        memset(go, 0sizeof(go));
    }
    ~Trie() {
        for (int i = 0; i<2; i++)
            if (go[i]) delete go[i];
    }
    void insert(const char* key) {
        if (*key == '\0') {
            return;
        }
        int next = *key - '0';
        if (!go[next]) {
            go[next] = new Trie;
        }
        return go[next]->insert(key + 1);
    }
    void query(char* key) {
        if (*key == '\0') {
            return;
        }
        int next = *key - '0';
        next ^= 1;
        if (go[next]) {
            *key = '1';
            return go[next]->query(key + 1);
        }
        else {
            *key = '0';
            return go[next ^ 1]->query(key + 1);
        }
    }
};
int main()
{
    scanf("%d"&n);
    Trie *root = new Trie;
    for (int i = 0; i < n; i++)
        scanf("%d"&arr[i]);
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];
        for (int j = 31; j >= 0; j--)
        {
            if (x % 2)
                c[j] = '1';
            else
                c[j] = '0';
            x = x / 2;
        }
        c[32= '\0';
        root->insert(c);
    }
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];
        for (int j = 31; j >= 0; j--)
        {
            if (x % 2)
                c[j] = '1';
            else
                c[j] = '0';
            x = x / 2;
        }
        c[32= '\0';
        root->query(c);
        int y = 0;
        for (int i = 31; i >= 0; i--)
        {
            y += (c[i] - '0'* pow(231 - i);
        }
        res = max(res, y);
    }
    printf("%d", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)4948 베르트랑 공준  (0) 2017.01.06
BOJ)12842 튀김 소보루  (0) 2017.01.05
BOJ)13505 두수 XOR  (4) 2017.01.05
BOJ)12843 복수전공  (0) 2017.01.05
BOJ)12841 정보대 등산  (0) 2017.01.05
BOJ)1865 웜홀  (0) 2017.01.05
TAG
댓글
  • 프로필사진 백준 arr배열크기를 100,000이 아니라 100,010을 준 이유가 있나요? 2018.05.28 15:24
  • 프로필사진 JASON 자손9319 보통 문제를 풀 때 40byte정도의 메모리 사용은 큰 지장이 없기 때문에 오버플로우 방지로 넉넉하게 메모리를 사용하는게 습관이 되서 그렇습니다! 2018.05.28 20:16 신고
  • 프로필사진 질문 33-40 줄에서 go[next] 혹은 go[next^1]에서 query를 호출하게 되는데, 두 노드 모두 NULL일 가능성이 없나요? 2019.08.08 23:11
  • 프로필사진 질문 모든 리프노드의 레벨이 같으니까 자연스럽게 그렇게 되는군요. 2019.08.09 00:37
댓글쓰기 폼