취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24501번 문제인 blobaww이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/24501 

맨 왼쪽 위에서부터 표를 읽으면서, 그 칸의 행과 열까지만을 포함하는 부분행렬에서 만들어질 수 있는 "E", "ES", "ESM"의 개수를 점화관계를 이용하여 계산해나가자.

지금 써져있는 문자가 E라면 이 칸까지의 E의 개수에 1을 하나 더하고, S라면 이 칸까지의 S의 개수에 "E의 개수"를 더하고, M이라면 이 칸까지의 M의 개수에 "S의 개수"를 더해주면 문제에서 요구하는 경우의 수를 구할 수 있다.

나머지 계산 처리에 주의하자.

아래는 제출한 소스코드이다.

#define MAX 1000000007
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

string board[3000];
ll E[3000][3000];
ll S[3000][3000];
ll M[3000][3000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int R, C; cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			ll e1 = 0, e2 = 0, e3 = 0, s1 = 0, s2 = 0, s3 = 0, m1 = 0, m2 = 0, m3 = 0;
			if (r) e1 = E[r - 1][c], s1 = S[r - 1][c], m1 = M[r - 1][c];
			if (c) e2 = E[r][c - 1], s2 = S[r][c - 1], m2 = M[r][c - 1];
			if (r && c) e3 = E[r - 1][c - 1], s3 = S[r - 1][c - 1], m3 = M[r - 1][c - 1];
			E[r][c] = e1 + e2 - e3, S[r][c] = s1 + s2 - s3, M[r][c] = m1 + m2 - m3;
			if (board[r][c] == 'E') E[r][c]++;
			else if (board[r][c] == 'S') S[r][c] += E[r][c];
			else M[r][c] += S[r][c];
			E[r][c] %= MAX, S[r][c] %= MAX, M[r][c] %= MAX;
			if (E[r][c] < 0) E[r][c] += MAX;
			if (S[r][c] < 0) S[r][c] += MAX;
			if (M[r][c] < 0) M[r][c] += MAX;
		}
	}

	cout << M[R - 1][C - 1];
}