문제

문제 링크

문제 접근

  • 이 문제는 그리디로 풀 수 있는 문제이다.
  • 왜 그리디인지는 나도 다른 블로그를 참고하고 나서야 알았다…

그리디인 이유

  • 물론 3*3을 다 바꾸긴하지만 왼쪽 끝에서 부터 시작해서 바꾸기 시작한다면 [0][0]~[2][2]까지 업데이트 한 후에는 [0][0]의 값은 변하지 않게 된다.
  • 즉, 3*3의 왼쪽 위의 점은 이제 변하지 않고 고정될 것임으로 왼쪽 위부터 오른쪽 아래까지 각 위치의 값을 비교하면서 같지 않은 경우에 뒤집기를 반복한다면 정답을 찾을 수 있다.

코드

#include <cstdio>
int n, m, cnt, arr[2][51][51];
int main(){
    scanf("%d %d", &n, &m);
    for(int k = 0; k < 2; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++)scanf("%1d", &arr[k][i][j]);
        }
    }
    for(int i = 0; i < n - 2; i++){
        for(int j = 0; j < m - 2; j++){
            if(arr[0][i][j] == arr[1][i][j])continue;
            cnt++;
            for(int k = 0; k < 3; k++){
                for(int l = 0; l < 3; l++){
                    arr[0][i+k][j+l] = !arr[0][i+k][j+l];
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(arr[0][i][j] != arr[1][i][j]){
                cnt = -1;
                break;
            }
        }
    }
    printf("%d", cnt); 
}

느낀점

  • 이 문제가 그리디라는 것을 전혀 예상치도 못했다…
  • 문제를 볼 때 접근법에 그리디가 있음을 의식하도록 연습해야겠다.