14457 Cow Tipping

10*10 그리드를 주고 맨 왼쪽 위를 반드시 포함하는 rectangle 을 flip시킬 수 있을 때

최소 몇번만에 모든 그리드를 0으로 만들 수 있는지 물어보는 문제다.

그리드를 s[n][n]이라고 하자.

s[i][j] == 1이라면 이걸 flip시키려면

0,0 ~ k,l ( k>=i, l>=i ) 에서 flip시켜야 한다.

만약 n-1,n-1 번째가 1이라면 반드시 전체를 flip시켜야 한다는 뜻이다.

따라서 그리디하게 n-1,n-1부터 0,0까지 훑어보면서 s[i][j] == 1이라면 flip시킨다.

#include <iostream>
using namespace std;
 
int n, ans;
char s[10][11];
 
void flip(int i,int j) {
    for (int k = 0; k <= i; ++k) for (int l = 0; l <= j; ++l)
        s[k][l] = s[k][l] == '1' ? '0' : '1';
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> s[i];
    for (int i = n - 1; i >= 0; --i) for (int j = n - 1; j >= 0; --j) {
        if (s[i][j] == '1') {
            ans++;
            flip(i, j);
        }
    }
    cout << ans << '\n';
    return 0;
}