[BOJ] 백준 11811 데스스타

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

Approach

※ 비트마스크 (Bitmask) 

비트마스크 (Bitmask)

Input Data에서 마지막 행은 다음과 같다.

m4i =

▶ m40 = 1 = a4 & a0 

    11 & 1 → 1011 & 0001 = 0001

▶ m41 = 2 = a4 & a1 

    11 & 2 → 1011 & 0010 = 0010

▶ m42 = 3 = a4 & a2 

    11 & 3 → 1011 & 0011 = 0011

▶ m43 = 1 = a4 & a3 

    11 & 1 → 1011 & 0001 = 0001

 

각 행의 모든 값을 OR 연산하면 답을 얻을 수 있습니다.

▶ a[i] = a[i] | m[i][j]

    (초기 a[i] = 0)

 

---

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int a[1001];
int main(){
    int n, m;
    cin >> n;
 
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            cin >> m;
            // 주대각선에 있는 값은 무시
            // 0으로 입력받기에 OR 연산처리 시켜도 무방
            if (i == j) continue;
            a[i] = a[i] | m;
        }
    }
 
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    
}