Problem D 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1547/problem/D

배열 x가 growing이 되기 위해서는 xi-1 & xi = xi-1 이어야 한다.

xi-1 & xi = xi-1이 나오려면 xi-1의 이진수에서 값이 1인 자리가 xi의 이진수에서의 값이 1이어야 한다.

즉, 예를 들면 이진수 10100과 & 연산하여 10100이 나오려면 이진수 1x1xx와 계산되어야 한다.

여기서 x는 1이나 0이나 아무 상관이 없다.

그렇다면 배열 x의 모든 원소가 배열 y의 모든 원소와 XOR 연산을 한 배열이 growing이 되기 위해서는 xi ^ yi를 xyi라고 할 때, xyi-1 & xyi = xyi-1이 되어야 한다.

그렇다면 xyi는 xyi-1의 이진수에서 값이 1인 자리의 값만 1이면 된다는 의미다.

XOR 연산에서 값이 1이 되려면 두 개의 값 중 하나만 1이면 된다.

때문에 xi만 알고있는 상황에서 yi를 알기 위해서는 위의 1이어야만 하는 자리를 xi에서 확인하고 해당 값의 반대 값을 yi의 해당 자리의 값으로 정한다.

그리고 나머지 자리의 값은 0으로 정한다.

이유는 만족하는 배열 y 중 최소 값이어야 한다는 조건이 있기 때문이다.

나머지 자리의 값은 어떤 것이든 상관없으므로 0으로 정한다.

위와 같은 이유로 y0은 무조건 0이 된다.

초기에 y0를 아는 상태에서 y1부터 값을 구한다.

값을 구하는 과정은 아래와 같다.

1. xi-1 ^ yi-1의 이진수 값을 구한다.

2. xi의 이진수 값을 구한다.

3. 1번의 이진수에서 값이 1인 자리를 확인하여 xi의 이진수에서 해당 자리들의 반대 값을

    yi의 이진수의 해당 자리들의 값으로 정한다. 나머지 자리의 값은 모두 0으로 한다.

이 과정을 반복하여 배열 y의 모든 원소를 구한다.


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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> numTobinary(int num) {
    vector<int> binary(30, 0);
    int index = 0;
    while (num != 0) {
        binary[index] = num % 2;
        num /= 2;
        index++;
    }
    return binary;
}
 
int binaryTonum(vector<int> binary) {
    int num = 0;
    int b = 1;
    for (int i = 0; i < 30; i++) {
        num += binary[i] * b;
        b *= 2;
    }
    return num;
}
 
int main() {
 
    int t;
    cin >> t;
    
    while (t--) {
 
        int n;
        cin >> n;
 
        vector<int> x(n), y(n);
 
        for (int i = 0; i < n; i++)
            cin >> x[i];
 
        y[0] = 0;
 
        for (int i = 1; i < n; i++) {
            vector<int> before = numTobinary(x[i - 1] ^ y[i - 1]);
            vector<int> binaryX = numTobinary(x[i]);
            vector<int> binaryY(30, 0);
 
            for (int i = 0; i < 30; i++)
                if (before[i] == 1)
                    binaryY[i] = (binaryX[i] == 0) ? 1 : 0;
 
            y[i] = binaryTonum(binaryY);
        }
 
        for (auto a : y)
            cout << a << " ";
        cout << endl;
 
    }
 
    return 0;
}
cs

댓글

댓글 쓰기