14494번 - 다이나믹이 뭐에요?

이차원 배열이 주어질 때 시작점에서 끝점까지 가는데의 최단 경로의 수를 구하는 문제입니다.
문제에서 구체적으로 명시하지는 않았는데, 최단 경로가 맞습니다.

분석

먼저 최단 경로는 이러한 식으로 생겼습니다.
문제에서 친절히 맨 위에서 아래,오른쪽으로만 가는 최단 경로의 점화식은

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

이라고 언급이 되어있습니다.
하지만 문제는 아래와 오른쪽 뿐만이 아닌 대각선으로도 이동이 가능하다고 되어있습니다.
그래서 점화식에 대각선을 추가하게 되면

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

라는 점화식 도출이 가능해집니다.

이제 코딩에 들어갈껀데, 주의할 점은 세로축[0]과 가로축[0]은 위에 그림에 보시다시피 전부 1로 초기화를 진행해야 (해당 행/렬은 접근 가능한 경우의 수가 단 하나) 해당 점화식이 의미가 있습니다.

코딩

n,m = map(int,input().split())
dp = [[0]*m for _ in range(n)]
dp[0][0] = 1
for a in range(n):
    dp[a][0] = 1
for b in range(m):
    dp[0][b] = 1

이차원배열을 하나 선언하고 가로축의 0번째, 세로축의 0번째 행/열을 전부 1로 초기화해줍시다.

for i in range(len(dp)):
    for j in range(len(dp[i])):
        if i == 0 or j == 0:
            continue
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1] 

초기화한 라인을 제외한 구간은 전부 도출한 점화식을 적용시켜줍시다.

print(dp[n-1][m-1]%1000000007)

1000000007로 나눈 나머지를 문제에서 요구한대로 출력해줍시다.