[BOJ] 백준 15924 욱제는 사과팬이야!!

문제 링크

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

구사과씨가 어디서 출발할지 모른다. 따라서 각각의 모든 점에서 X까지 갈 수 있는 경우의 수를 모두 구해서 더해야 한다. 역으로 X에서부터 시작해 뒤쪽에서 앞쪽으로 올 수 있는 경우의 수를 저장하자.

$d[i][j] = (i, j)$에서 X까지 갈 수 있는 경로의 수

$p[i][j] =$ 직사각형 지도에서 $(i, j)$의 정보 

$\left\{\begin{array}{c}d[i-1][j] = d[i-1][j] + d[i][j],\text{ if }\ i - 1 \geq 0 \text{ and } p[i-1][j] = \text{'S' or 'B'} \\ d[i][j-1] = d[i][j-1] + d[i][j],\text{ if }\ j - 1 \geq 0 \text{ and } p[i][j-1] = \text{'E' or 'B'} \end{array}\right.$

점화식을 세웠으니 반복문을 돌리자. 연산할때마다 $10^9+9$로 나눠주는 것을 잊으면 안된다.

정답 코드

	#include <iostream>
	#include <string>
	using namespace std;
	const int MOD = 1000000009;
	int n, m, d[3001][3001];
	string p[3001];
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	cin >> p[i];
	d[n - 1][m - 1] = 1;
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) {
	for (int j = m - 1; j >= 0; j--) {
	ans += d[i][j] % MOD; // d[i][j]는 이미 구했으므로 바로 답에 더해준다
	ans %= MOD;
	if (i - 1 >= 0 && (p[i - 1][j] == 'S' || p[i-1][j] == 'B')) {
	d[i - 1][j] += d[i][j] %MOD;
	d[i - 1][j] %= MOD;
	}
	if (j - 1 >= 0 && (p[i][j - 1] == 'E' || p[i][j - 1] == 'B')) {
	d[i][j - 1] += d[i][j]%MOD;
	d[i][j - 1] %= MOD;
	}
	}
	}
	cout << ans;
	}

view raw 15924.cpp hosted with ❤ by GitHub

질문, 피드백 환영합니다.