[BOJ] 1034 램프

문제 링크

 

www.acmicpc.net/problem/1034

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

이 문제를 풀기 위해 나는 먼저 주어진 2차원 배열의 열을 2진수로 바꿔서 생각했다. 예제로 주어진 배열에서 보면 첫 번째 열은 위에서부터 0, 1, 1이므로 011(2), 두 번째 열은 위에서부터 1, 0, 0이므로 100(2)와 같이 바꿔보면 특정 열의 스위치를 누르는 것은 그 열의 수와 bit 1이 n개인 수(2^n - 1)와 XOR 연산을 하는 것이라고 생각할 수 있다. 행과 열이 최대 50개까지 늘어날 수 있으므로 각각의 열을 나타내는 수는 long long 형으로 설정했다.

 

이렇게 생각을 해보면 이 문제는 임의의 열들을 골라 bit 1이 n개인 수(2^n - 1)와 K번 XOR 연산을 수행한 뒤, 전부 AND 연산한 수에서 bit 1의 갯수를 세는 문제로 바꿔서 생각할 수 있다. bit 1의 갯수가 최대가 되는 경우를 찾기 위해 첫 번째 행부터 마지막 행까지 for문을 돌며 bit가 0인 열은 XOR 연산을 해준 뒤 (2^n - 1)로 초기화한 변수 sum과 AND 연산을 해주고,  1인 열은 그대로 sum과 AND 연산을 해준다. 이 과정에서 XOR 연산의 횟수가 k번을 넘거나 남은 횟수가 홀수일 경우는 결과에서 제외해줬다. 계산을 편리하게 하기 위해 세 가지의 메소드를 정의했다.

 

bool chk(ll num, int digit) { // num의 digit자리 bit가 1인지 0인지 확인하는 함수
							  // 1이면 true, 0이면 false return
	return num & ((1ll) << (n-digit-1));
}

ll reverse(ll num) { // num의 bit 0 -> 1로, 1 -> 0으로 변환하는 함수 
	return num ^ maxa;
}

int count(ll sum) { // 변수 sum에서 bit 1의 갯수를 세는 함수
	int ret = 0;
	while (sum > 0) {
		if (sum & 1) ret++;
		sum >>= 1;
	}
	return ret;
}

 

전체 코드는 아래와 같다.

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
ll num[50];
int n, m;
ll maxa; // n자리까지 모두 1인 이진수
char board[50][50];

bool chk(ll num, int digit) { // num의 digit자리 bit가 1인지 0인지 확인하는 함수
							  // 1이면 true, 0이면 false return
	return num & ((1ll) << (n-digit-1));
}

ll reverse(ll num) { // num의 bit 0 -> 1로, 1 -> 0으로 변환하는 함수 
	return num ^ maxa;
}

int count(ll sum) { // 변수 sum에서 bit 1의 갯수를 세는 함수
	int ret = 0;
	while (sum > 0) {
		if (sum & 1) ret++;
		sum >>= 1;
	}
	return ret;
}

int main() {
	int i, j, k;
	cin >> n >> m;
	maxa = (((1ll) << n) - 1);
	for (i = 0; i < n; i++) {
		cin >> board[i];
	}
	cin >> k;

	// 각 열을 숫자로 나타내기
	for (i = 0; i < m; i++) { //열
		for (j = 0; j < n; j++) { //행
			num[i] += board[j][i]-'0';
			if(j!=n-1) num[i] <<= 1;
		}
	}

	int ret = 0;
	for (i = 0; i < n; i++) {
		int remain = k;
		long long sum = maxa; // 각 열들 and 연산한 결과가 들어감.
		for (j = 0; j < m; j++) {
			if (!chk(num[j], i)) { // num[j]의 2^i 자리가 0인 경우
				sum &= reverse(num[j]);
				remain--;
			}
			else sum &= num[j];
		}
		if (remain < 0 || remain % 2 == 1) continue; // XOR 연산 횟수가 k번을 넘기거나
                                                     // 남은 연산 횟수가 홀수인 경우
                                                     // -> 연산 횟수 k번을 채우기 위해 최소 1개의 열이 
                                                     //0->1, 1->0으로 뒤집혀야 하고, 그러면 sum이 달라진다.
                                                     //따라서 제외
		ret = max(ret, count(sum));
	}
	cout << ret << endl;
}