[11811번] 데스스타

문제 출처 :

https://www.acmicpc.net/problem/11811

알고리즘 분석 :

문제 해결에 필요한 사항

1. 비트 연산

최소 정답을 찾는게 아닌 답이 될 수 있는 아무 정답이나 찾으면 되는 문제이다.

and연산을 통해 나타난 input이니 or연산을 통해 값을 찾아내주면 and시에도 그 값을 얻어 낼 수 있게 된다.

(and가 교집합이면 or가 합집합인 느낌으로 생각하면 된다.)

그후 max를 이용하여 or연산에서 가장 최대로 나오는 값을 적용시켜주자.

이때 ans[i] |= arr[i][j]로 바꾸어도 무방하다.(모든 값을 or연산해준다는 의미) 

소스 코드 : 

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

#include <iostream> #include <cstdio> #include <algorithm> using namespace std;   int arr[1002][1002]; int ans[1002];   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             scanf("%d", &arr[i][j]);         for(int i = 0 ; i < n ; i ++)         for (int j = 0; j < n; j++)         {             if (i == j)                 continue;               ans[i] = max(ans[i], arr[i][j] | arr[j][i]);         }       for (int i = 0; i < n; i++)         printf("%d ", ans[i]);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus