[알고리즘 문제 풀기] 다이나믹이 뭐예요?(14494)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있따.

2. 나의 정답 코드

StreamReader sr = new(Console.OpenStandardInput());
StreamWriter sw = new(Console.OpenStandardOutput());
string[] split = sr.ReadLine().Split();
int n = int.Parse(split[0]);
int m = int.Parse(split[1]);
long[,] dp = new long[n + 1, m + 1];
dp[0, 0] = 1;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        dp[i, j] = (dp[i - 1, j - 1] + dp[i - 1, j] + dp[i, j - 1]) % 1000000007;
    }
}
sw.WriteLine(dp[n, m]);

sr.Close();
sw.Close();

3. 정리

• 초기값으로 dp[0, 0] = 1을 설정한다.

• 이중 반복문을 통해 dp[i, j] 값을 갱신한다.
• dp[i, j]는 이전 상태들(dp[i-1, j-1], dp[i-1, j], dp[i, j-1])의 합을 사용하여 계산한다.
• 값을 계산할 때 1000000007로 나눈 나머지를 저장한다.

• 최종적으로 dp[n, m] 값을 출력한다.