BOJ 14494번: 다이나믹이 뭐예요?

www.acmicpc.net/problem/14494

14494번: 다이나믹이 뭐예요?

 

아이디어:

 

"오른쪽, 아래쪽으로만 움직일 수 있을 때, D[1][1]에서 D[x][y]까지 도달하는 경우의 수를 구하는 문제는 일일히 모든 경우를 다 계산할 필요 없이, D[i][j] = (i, j)에 도달하는 누적 경우의 수 = D[i-1][j] + D[i][j-1]를 세워서 해결할 수도 있죠."

 

문제에서는 →, ↓, ↘의 세 방향을 사용하므로 

dp[i][j] = dp[i][j-1] + dp[i-1][j] + dp[i-1][j-1]

 

import sys
n, m = map(int, sys.stdin.readline().split())
dp = [[0]*(m+1) for _ in range(n+1)]

#(1,1)~(1,n), (1,1)~(1,m)까지 1로 초기화
for i in range(1, n+1):
    dp[i][1]=1
for j in range(1, m+1):
    dp[1][j]=1
    
for i in range(2,n+1):
    for j in range(2,m+1):
        dp[i][j] = dp[i][j-1] + dp[i-1][j] + dp[i-1][j-1] #각각 →, ↓, ↘로 움직이는 경우
print(dp[n][m]%1000000007)

※ 배열의 크기를 설정하는 부분에서 제일 위의 인덱스가 (1,1)인데 n*m크기로 설정해서 헤맸었다.