6731. 홍익이의 오델로 게임

#include<cstdlib>
#include<cstring>
#include<iostream>
 
using namespace std;
 
int tc;
int n;
char map[1000][1000];
int ans;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>tc;
    for(int t = 1; t<= tc; t++){
         
        ans = 0;
        int r[1000] = {0,};
        int c[1000] = {0,};
         
        cin>>n;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin>>map[i][j];
                if(map[i][j] == 'B'){
                    r[i]++;
                    c[j]++;
                }
            }
        }
 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int x = r[i] + c[j];
                if(map[i][j] == 'B'){
                    x-=1;
                }
                if(x % 2 != 0){
                    ans++;
                }
            }
        }
         
         
        cout<<"#"<<t<<" "<<ans<<'\n';
    }
    return 0;
}

규칙을 찾지않으면 풀수없는 문제다.

규칙을 찾으면 위와같은 풀이를 생각해볼수있는데

일단 그전에, 배열의크기자체가 1000 x 1000배열에, 시간제한이 1초인 문제에서 브루트포스나 백트래킹 같은 모두다해보는 알고리즘은 쓸수없는것을 판단해야 했고

그때부터 DP를 선택해야할지, 규칙성을 찾아야할지 생각해봐야했는데, 아무리봐도 점화식세우기 어려울것같았다.

문제에서 규칙성을 생각해보면서 행과 열로 나누는 방식을 선택해서 문제를 풀어나갔고, 위와같은 풀이를도출할수있었다.

처음에 scanf, printf만하려했는데, 상당히 까다로울것같아서 그냥 cin,cout하고 속도빠르게진행해서 풀어낸 문제