취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11811번 문제인 데스스타이다.
문제는 아래 링크를 확인하자.

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

두 양의 정수 $a$와 $b$에 대하여 $a\mathrm{\&}b$ (단, $\mathrm{\&}$는 bitwise and 연산이다.)의 값을 $k$라 한다면 적어도 $a$와 $b$는 $k$에서 1로 나타나는 비트가 항상 1이어야 함을 알 수 있다. 이 성질을 이용하면 각 $a_i$와 $a_j$의, 1이어야 하는 최소한의 비트를 전부 구할 수 있다.

위에서 구한 비트가 문제의 답이 될 수 있음은 어렵지 않게 보일 수 있으므로 증명은 생략한다. (귀류법을 사용해보자.) 문제의 답이 유일하지 않을 수 있는 이유는 각 수에 다른 수에서 전혀 등장하지 않은 자릿수의 비트를 하나씩 끼워넣어도 문제의 답이 될 수 있기 때문이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int A[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			int x; cin >> x;
			A[r] |= x, A[c] |= x;
		}
	}
	for (int i = 0; i < N; i++) cout << A[i] << ' ';
}