[BOJ 1034] 램프

BOJ 1034 램프

유형

• 브루트포스

풀이

처음에는 풀이방법이 떠오르지 않아서 한줄씩 껐다켰다하는 방식을 재귀로 구현하였지만 최대 2^50의 경우의 수가 있으므로 당연히 시간초과가 났다. 풀이가 떠오르지 않아서 다른 사람들의 코드를 참조하였다.

행의 전구가 꺼져있고 켜져있는 패턴이 같으면 열단위로 스위치를 조작했을 때 다같이 꺼지고 켜질 것이다. 그렇기 때문에 k번 스위치를 조작하였을 때 다 켜져 있으면서 최대한 동일한 패턴이 많은 행을 찾으면 정답을 얻을 수 있었다.

행의 꺼져있는 스위치의 개수를 찾아서 다음 조건을 만족하는지 검사한다.

1. 행의 꺼져있는 스위치 개수가 k개보다 작거나 같은지
2. 행의 꺼져있는 스위치 개수와 k개가 둘다 짝수이거나 홀수인지

행의 꺼져있는 스위치 개수보다 k가 작게되면 그 행의 전구를 다 킬 수 있는 방법은 없다. 그리고 행의 꺼져있는 스위치 개수보다 k가 클 때는 똑같이 짝수이거나 홀수여야 한다.

그 이유는 예를 들어 꺼져있는 전구의 개수가 5개 일때 k는 5,7,9... 이러한 값들을 가져야 행의 모든 전구를 킬 수 있기 때문이다. 다시 말하면 꺼져있는 5개의 전구를 전부 킨 후 2,4,6..번의 동작은 원래 5개의 전구를 킨 상태와 같은 상태를 만들 수 있다는 것이다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <time.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m, k;
string arr[51];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> arr[i];
	cin >> k;

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int j = 0; j < m; j++)
			if (arr[i][j] == '0') cnt++;

		int s = 0;
		if (cnt <= k && cnt % 2 == k % 2) {
			for (int j = 0; j < n; j++) {
				if (arr[i] == arr[j]) s++;
			}
		}
		ans = max(ans, s);
	}
	cout << ans;

	return 0;
}