[백준 14494번] 다이나믹이 뭐에요? (C++)

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

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define per 1000000007
int n, m;
long long dp[1001][1001];

int main()
{
	fastio;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)  // 첫 번째 줄 → 방향 전부 1로 초기화 (초기값)
	{
		dp[i][1] = 1;
	}
	for (int i = 1; i <= m; i++)  //첫 번째 줄 ↓ 방향 전부 1로 초기화 (초기값)
	{
		dp[1][i] = 1;
	}

	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j <= m; j++)
		{
			dp[i][j] = (dp[i - 1][j - 1] + dp[i][j - 1] + dp[i - 1][j]) % per;  //점화식
		}
	}
	cout << dp[n][m] % per;
}

첫 번째 줄 좌측방향과 아래쪽 방향은 경우의 수가 1가지 밖에 없으므로 1로 초기화해준다.

이동 방법은 3가지 밖에 없으므로 다음 값들은 3가지 방법으로 이동하기 전의 값들을 더해주면 된다.

또한 범위가 크기에 dp는 long long으로 선언하고 조건에 따라 해당 값마다 미리 선언한 값 per(1000000007)로 나눠줬다.