[코드트리] 0과 1로 이루어진 격자 C++

문제

https://www.codetree.ai/missions/8/problems/grid-consisting-of-0-and-1?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 쪼개기

주어지는 것

정수 N

숫자 0과 1로만 이루어진 N * N 크기의 격자

목표

모든 칸을 0으로 만들려고 할 때, 칸을 누르는 횟수를 최소화

조건

 특정 칸을 누르면 그 칸을 기점으로 좌측 상단 모든 영역을 반전(0→1, 1→0)

 

 

마지막 칸부터 반전시키면 해당 칸에 영향을 줄 수 있는 곳이 해당 칸 밖에 없으므로 최소 횟수가 될 것 같다(아래 그림 참고)

코드

#include <iostream>
using namespace std;

const int MAX_N =11;

int n;
string arr[MAX_N];

void Reversing(int x, int y){
    for(int i=0; i<=x; ++i){
        for(int j=0; j<=y; ++j){
            if(arr[i][j]=='1') arr[i][j]='0';
            else arr[i][j]='1';
        }
    }
}

int main() {
    cin >> n;
    for(int i=0; i<n; ++i){
        cin >> arr[i];
    }
    
    // 모든 칸을 0으로 만들려고 할 때, 칸을 누르는 횟수를 최소화하는 프로그램을 작성
    int answer=0;
    for(int i=n-1; i>=0; --i){
        for(int j=n-1; j>=0; --j){
            if(arr[i][j]=='1'){
                Reversing(i, j);
                answer++;
            }
        }
    }
    cout << answer << '\n';
    return 0;
}