[백준/CPP] 뒤집기 II - 1455번

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

1455번: 뒤집기 II

 

 

일정한 규칙이 있다.

위처럼 어떠한 동전을 뒤집으면 해당 행 + 열까지의 동전은 모두 뒤집힌다.

그러므로 n행 m열부터 시작하여 맨 처음 뒤집힌 동전(1)이 나오는 곳을 찾는다.

해당 부분부터 동전을 뒤집기 시작하면 답을 구할 수 있다.

 

ex) (3,2)는 (1,1) 번째 동전에 영향을 줄 수 있지만 (1,1) 동전은 (3,2) 동전에 영향을 줄 수 없음!

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m; cin >> n >> m;

	vector <char> vc2(m, 0);
	vector <vector <char>> vc(n, vc2);

	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		for (int j = 0; j < s.length(); j++) {
			vc[i][j] = s[j];
		}
	}

	// prt(vc);
	int cnt = 0;

	for (int i = n - 1; i > -1; i--) {
		for (int j = m - 1; j > -1; j--) {
			if (vc[i][j] == '1') {
				cnt++;
				for (int k = 0; k <= i; k++) {
					for (int l = 0; l <= j; l++) {
						if (k <= i && l <= j) {
							if (vc[k][l] == '0')
								vc[k][l] = '1';
							else
								vc[k][l] = '0';
						}
					}
				}
			}
		}
	}

	// prt(vc);

	cout << cnt;

}