[백준] 14494번 다이나믹이 뭐예요?

💡문제접근

• 직접 표를 그려서 점화식을 세운 결과 나온 점화식은 아래와 같다.

dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i][j-1]) % 1000000007

• 테스트케이스1 입력 데이터를 기반으로 표를 그려보면 다음과 같다.

💡테스트케이스1

입력
3 2

출력
5

1	1
1	3
1	5

💡테스트케이스2

입력
4 5

출력
129

1	1	1	1	1
1	3	5	7	9
1	5	13	25	41
1	7	25	63	129

💡코드(메모리 : 70776KB, 시간 : 604ms)

import sys
input = sys.stdin.readline

n, m = map(int, input().strip().split())

dp = [[1 for _ in range(m+1)] for _ in range(n+1)]

for i in range(1, n):
    for j in range(1, m):
        dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i][j-1]) % 1000000007
print(dp[n-1][m-1])

💡소요시간 : 7m