[백준 22983 ] 조각 체스판

#include <bits/stdc++.h> 
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 987654321
using namespace std;

int row[3001][3001];
int col[3001][3001];
int dp[3001][3001];
int board[3001][3001];
int N, M;

int main() {
	cin >> N >>M;
	FASTIO;
	//입력
	string str ="";
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int j = 0; j < M; j++) {
			if (str[j] == 'B') {
				board[i][j] = 0;
			}
			else if(str[j] == 'W'){
				board[i][j] = 1;
			}
			dp[i][j] = 1;
			
			row[i][j] = 0;
			col[i][j] = 0;
		}
	}
	//ROW COL 값 계산
	for (int i = 1; i < N; i++ ) {
		for (int j = 1; j < M; j++) {
			if (board[i][j] != board[i][j - 1])
				row[i][j] = row[i][j - 1] + 1;
			else
				row[i][j] = 0;
			if (board[i][j] != board[i - 1][j ])
				col[i][j] = col[i-1][j] + 1;
			else
				col[i][j] = 0;
		}
	}
	//DP 결과 계산 
	long long  ans =0;
	for (int i = 1; i < N; i++) {
		for (int j = 1; j < M; j++) {
			if (board[i][j] == board[i - 1][j - 1]) {
				//cout << i << " " << j << "\n";
				dp[i][j] = min({ dp[i - 1][j - 1], row[i][j], col[i][j] });
				dp[i][j]++;	
			}
			else
				dp[i][j] = 1;
				
			ans += dp[i][j];
		}
	}
	cout << ans + N + M - 1;	
}

결과를 int로 했더니 틀려서 longlong으로 바꿔서 성공했다.

 

 다이나믹 프로그래밍은 코딩은 쉬운데 발상이 너무 어렵고 힘들다 ..

너무 힘든 문제였다  ..