백준14494 다이나믹이 뭐예요?

작성일 | In

문제 링크

  • http://icpc.me/14494

문제 출처

  • 2017 선린 봄맞이 대회 H번

사용 알고리즘

  • DP

시간복잡도

  • O(nm)

풀이

(i, j)에서 갈 수 있는 곳은 (i+1, j), (i, j+1), (i+1, j+1) 총 3가지입니다.
다른 의미로는 (i, j)로 가기 위해서는 (i-1, j), (i, j-1), (i-1, j-1) 중 하나를 거쳐야 한다는 것입니다.
(i, j)로 가는 경우의 수는 { (i-1, j)까지 가는 경우의 수 } + { (i, j-1)까지 가는 경우의 수 } + { (i-1, j-1)까지 가는 경우의 수 }라고 할 수 있습니다.

점화식을 그대로 코드로 옮기면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
long long dp[1010][1010]={0};

int main(){
	dp[1][1]=1;
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(i*j!=1) dp[i][j] = (dp[i][j-1]%mod + dp[i-1][j]%mod + dp[i-1][j-1]%mod)%mod;
		}
	}
	printf("%lld", dp[n][m]%mod);
}