[PS] (백준 1080번) 행렬 C++

전체 코드는 가장 하단에 있습니다 ~

문제 이해

왜 그리디인지 이해가 잘 안됐었는데

왼쪽 상단 [0][0] 자리 숫자가 target 값과 다르면

그 값을 기준으로 3x3 으로 모든 값을 변경해주고

그담에 [0][0] 위치를 옆으로 옮기고 ... 이런 식으로 해서 풀면 됐다

생각보다 금방 풀어서 놀랐음

 

반례

1 1

1

1

답 : 0

 

1 1

1

0

답 : -1

 

N, M이 3보다 작다고 해서 무조건 -1이 출력되는건 아니었다

 

전체 코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int data[51][51];
	int target[51][51];
	int N, M;
	int cnt = 0;
	cin >> N >> M;

	string input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		for (int j = 0; j < M; j++) {
			data[i][j] = input[j] - '0';
		}
	}

	for (int i = 0; i < N; i++) {
		cin >> input;
		for (int j = 0; j < M; j++) {
			target[i][j] = input[j] - '0';
		}
	}

	if (N < 3 || M < 3) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (data[i][j] != target[i][j]) {
					cout << -1;
					return 0;
				}
			}
		}
		cout << 0;
	}

	else {
		for (int i = 0; i < N - 2; i++) {
			for (int j = 0; j < M - 2; j++) {
				if (data[i][j] != target[i][j]) {
					for (int k = i; k < i + 3; k++) {
						for (int l = j; l < j + 3; l++) {
							data[k][l] = 1 - data[k][l];
						}
					}
					cnt += 1;
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (data[i][j] != target[i][j]) {
					cout << -1;
					return 0;
				}
			}
		}
		 cout << cnt;
	}

}