[백준] 15924-욱제는 사과팬이야!!(C++)

문제링크: https://www.acmicpc.net/problem/15924

15924번: 욱제는 사과팬이야!!

dp문제이고 top-down방식으로 해결하였다.

 

접근방식

 

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

 

2. top-down방식으로 쉽게 해결이 가능하다.

 

 

문제풀이 

 

1.  모든 좌표에서 도달 가능한 좌표를 탐색

이때, dp에 값을 저장해두었다가 같은 좌표를 탐색할때는 곧바로 반환해주는 형태로 구현

 

정답코드

 

 

#include <iostream>

using namespace std;

int n, m;
char arr[3001][3001];
long long dp[3001][3001];
long long result = 0;

long long solved(int y, int x) {
	if (y == n && x == m)
		return 1;

	long long& ret = dp[y][x];
	if (ret != -1)
		return ret;
	ret = 0;
	if (arr[y][x] == 'B') {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else if (arr[y][x] == 'E') {
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
	}

	ret %= 1000000009;

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			result += solved(i, j);

	cout << result % 1000000009 << endl;

	return 0;
}