백준 1034 램프 (c++) : 피너클

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

1034번: 램프

일종의 그리드 문제 같다.

우리는 열에 있는 램프의 상태를 바꿀수 있고 행에 있는 램프의 상태로 정답을 구한다.

하나의 열의 램프를 바꾸면 모든 행의 램프가 영향을 받는다.

예제 1을 예시로 들어보자.

0	1
1	0
1	0

위의 상태에서 첫번째 열을 바꾸면

1	1
0	0
0	0

위와 같이 된다. 만약 우리가 1행의 램프를 모두 킨 상태로 바꾼다면 아래 있는 행들중 

모두 킨 상태의 행은 처음부터 1행과 같은 상태의 행밖에 없다. 다시 예제 1을 예시로 들어보자.

0	1
1	0
1	0

우리는 1행과 2행 둘다 모든 램프가 켜진 상태로 만들수 없다.

1행 1열의 0을 1로 바꾸면 2열 1행의 1이 0으로 바뀌기 때문이다.

하지만 2행과 3행을 둘다 모든 램프가 켜진 상태로 만들수는 있다.

둘의 처음 상태가 같으니 2열의 모든 램프를 바꾸면 모든 램프가 1인 상태가 된다.

위와 같은 알고리즘으로 코드를 짜면 된다.

cin >> n >> m;
for (int i = 0; i < n; i++) cin >> sw[i];
cin >> k;

값들을 입력받은다음

int ans = 0;
for (int i = 0; i < n; i++) {
	int zero = 0;
	for (int j = 0; j < m; j++) {
		if (sw[i][j] == '0') zero++;
	}

int ans = 0을 선언한다. 정답을 여기에 담을것이다.

n만큼 반복문을 돌리며 시작한다.

int zero = 0을 선언한다. 한 행에 '0'이 들어있는 개수를 담는 변수다.

m만큼 반복문을 돌리며 만약 sw[i][j]가 '0'이면 zero에 1을 더한다.

	if (zero <= k && zero % 2 == k % 2) {
			ans = max(ans, chk(i));
		}
	}
	cout << ans << endl;

만약 0의 개수가 스위치를 누를수 있는 횟수보다 작거나 같고 둘다 짝수거나 홀수면 chk함수를 통해 ans를 바꾼다.

그후 ans를 출력한다.

zero와 k가 둘다 짝수거나 홀수여야 하는이유는 다음과 같다.

0

1

0

1

0

위와 같은 행이 있다고 하자. 위의 행을 전부 '1'로 바꾸려면 스위치를 총 3번 눌러야한다.

만약 스위치가 4번있다면 절대로 행의 전부를 '1'로 바꿀수 없다. 

하지만 5번 있다면 첫번째 0에 스위치를 3번 눌러 0 -> 1 -> 0 -> 1로 바꾸고 나머지 2번으로 나머지를 바꿀수있다.

바꿔야 하는 0의 개수가 홀수고 k가 짝수라면 절대로 모든 행을 1로 바꿀수 없다. 홀수와 짝수도 마찬가지다.

int chk(int num) {
	int ans = 0;
	for (int i = 0; i < n; i++) {
		bool chk = true;
		for (int j = 0; j < m; j++) {
			if (sw[i][j] != sw[num][j]) {
				chk = false;
				break;
			}
		}
		if (chk) ans++;
	}
	return ans;
}

chk함수는 다음과 같다.

단순히 모든 행과 열을 돌며 num번째 행과 같은 행의 개수를 찾아 리턴하면 된다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int n, m, k;
string sw[51];

int chk(int num) {
	int ans = 0;
	for (int i = 0; i < n; i++) {
		bool chk = true;
		for (int j = 0; j < m; j++) {
			if (sw[i][j] != sw[num][j]) {
				chk = false;
				break;
			}
		}
		if (chk) ans++;
	}
	return ans;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> sw[i];
	cin >> k;

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int zero = 0;
		for (int j = 0; j < m; j++) {
			if (sw[i][j] == '0') zero++;
		}
		if (zero <= k && zero % 2 == k % 2) {
			ans = max(ans, chk(i));
		}
	}
	cout << ans << endl;
}

전체코드다.