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

작성일 | In

문제 링크

  • http://icpc.me/15924

문제 출처

  • 제2회 천하제일 코딩대회 I번

시간복잡도

  • O(nm)

풀이

예선 B번 문제와 비슷하지만 풀이는 많이 다릅니다.
이 문제와 비슷한 방법으로 풀 수 있습니다.
현재 칸이 E인 경우, 오른쪽으로 갈 수 있습니다.
현재 칸이 S인 경우, 아래로 갈 수 있습니다.
현재 칸이 B인 경우, 오른쪽 또는 아래로 갈 수 있습니다.

dp[i][j]를 (n-1, m-1)에서 (i, j)까지 가는 방법의 수라고 정의합시다.
(i, j)가 E인 경우, dp[i][j] = dp[i][j+1]입니다.
(i, j)가 S인 경우, dp[i][j] = dp[i+1][j]입니다.
(i, j)가 B인 경우, dp[i][j] = dp[i][j+1] + dp[i+1][j]입니다.

점화식을 코드로 옮겨주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

const int mod = 1e9+9;

char ma[3010][3010];
int arr[3010][3010] = {0};

int main(){
	int n, m; scanf("%d %d", &n, &m);
	for(int i=0; i<n; i++) scanf("%s", ma[i]);
	arr[n-1][m-1] = 1;
	for(int i=n-1; i>=0; i--){
		for(int j=m-1; j>=0; j--){
			if(i == n-1 && j == m-1) continue;
			if(ma[i][j] == 'E') arr[i][j] = arr[i][j+1] % mod;
			if(ma[i][j] == 'S') arr[i][j] = arr[i+1][j] % mod;
			if(ma[i][j] == 'B') arr[i][j] = (arr[i][j+1]%mod + arr[i+1][j]%mod)%mod;
		}
	}

	int ans = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			ans += arr[i][j] % mod;
			ans %= mod;
		}
	}
	printf("%d", ans);
}