14494-다이나믹이 뭐에요?

다이나믹 프로그래밍의 이해를 돕기위해 간단한 다이나믹 프로그래밍 문제를 풀어보았다.

import sys
#sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230104/14494in.txt","r")
input = sys.stdin.readline

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

MAP = [[0 for _ in range(n)]for _ in range(m)]

for i in range(n):
  MAP[0][i]=1
for j in range(m):
  MAP[j][0] = 1

for i in range(1,m):
  for j in range(1,n):
    MAP[i][j] = MAP[i-1][j] + MAP[i][j-1] + MAP[i-1][j-1]

print(MAP[-1][-1]%1000000007)

아주간단한 다이나믹프로그래밍 문제로 각 경우의 수를 MAP에 메모라이징 해가면서 풀이하면 되는 문제이다.

우리가 고등학교 때 자주 풀던 "격자도착의 경우의 수"랑 같은 문제이다.

 

1. 먼저 MAP을 생성하고 [0][j], [i][0] 의 경우는 모두 도착할수있는 경우의 수가 1이기 때문에

모두 1로 설정을 해준다.

 

2. MAP[i][j]에 도착하는 경우의 수는 왼쪽 위쪽 그리고 왼쪽 위에서 오는 3가지 경우가 있고, 각 경우를 모두 더하주면 도착하는 경우의 수가 된다.

 

그래서 점화식은 MAP[i][j] = MAP[i-1][j] + MAP[i][j-1] + MAP[i-1][j-1]가 된다.

3. 가장 마지막으로 MAP[n-1][m-1]의 값을 출력하면 된다.