Codeforces Round #738 (Div. 2)-A. Mocha and Math

문제 설명

고등학생 지영은 학교 수학 선생님한테 매우 흥미로운 지식을 배우고 있다. 그 지식은 이진수와 이진수의 연산이다.

지영이에게 길이가 $n$인 수열 $a$이 주어진다. 지영은 무작위 구간 $[l, r]$을 선택해서 모든 $i (0 \le i \le r - l) $에 대해 $a_{i + 1}$을 $a_{i + 1} \wedge a_{r - i}$ 로 바꾸는 작업을 해야한다. 이때 $ \wedge$ 는 비트끼리 and 연산을 하라는 기호이다. 이 작업은 몇번이고 반복해도 상관 없다.

예를 들어 $n = 5$이고 배열이 $[a_1, a_2, a_3, a_4, a_5]$일 때, 지영이 구간 [2, 5]를 선택한다면 새로운 배열은 $[a_1, a_2 \wedge a_5, a_3 \wedge a_4, a_4 \wedge a_3, a_5 \wedge a_2]$가 된다.

지영이는 배열에 있는 값의 최대값을 최소로 만들어야 한다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 100)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 수열의 길이 정수 $n (1 \le n \le 100)$ 가 주어진다.

각 테스트 케이스의 두번째 줄에는 $n$개의 정수 $a_1, a_2, ..., a_n (0 \le a_i \le 10^9)$가 주어진다.

Output
각 테스트케이스마다 수열에 있는 최대값의 가장 작은 수를 출력한다.

Example
input
4
2
1 2
3
1 1 3
4
3 11 3 7
5
11 7 15 3 7

output
0
1
3
3

문제 접근

사용한 알고리즘: 구성적, 수학
걸린 시간 : 00:03
구성적 알고리즘이 A번에 나오니까 문제를 대회때 못푸는 기적이 일어났다. A번에서 10분 쓰고 계속 틀린답이 나오니까 결국 B번 문제로 넘어갔는데 B번하고 C번을 모두 풀고 다시 돌아와도 A번을 못풀었다. 멘탈 나가서 editorial을 보니까 푸는 방법은 단순한데 왜 이렇게 푸는지를 모르겠다. 이게 구성적 알고리즘인것 같다. 알면 그냥 풀고, 모르면 못푸는 문제.. 계속 공부해야겠다.

이런 bitmask문제가 꽤 자주 나오는 편인데, 이런 문제를 풀면서 가장 핵심적인 해결책이 논리 연산자의 성질이다. 그리고 이 성질은 비트 연산을 직접 노트에 적으면서 쭉 나열해 보면 보이는 경우가 많아서 다음부터는 시간이 걸리더라도 노트에 일일이 차근차근 나열해보자.

이 문제에서 연산을 계속 반복할 수 있다는 점 때문에 아래 방식으로 풀어도 되는 것 같다는 생각이다. 배열의 첫번째 값을 저장한 다음에 첫번째 이후의 수부터 계속 누적해서 AND연산을 진행한다. 왜냐하면 위에 있는 연산을 계속 반복하면 결국은 모든 원소끼리 AND연산한 값으로 모든 배열이 채워지기 때문이다. 또한 같은 값끼리 AND연산을 하면 값이 유지되기 때문에 한번만 AND연산을 하면 충분하다. $ A \wedge A = A$.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        int arr[n];
        for(int i = 0; i < n; i++) cin >> arr[i];
        int ans = arr[0];
        for(int i = 1; i < n; i++) ans &= arr[i];
        cout << ans << "\n";
    }
    return 0;
}