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

📌 BOJ 14494 다이나믹이 뭐예요?

💡 조건

1. 다이나믹 프로그래밍(동적 계획법), 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하다.

2. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 (= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션.)
   반복되는 똑같은 연산 횟수를 줄이는 것.

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

4. →, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 때, 왼쪽 위
   (1, 1)에서 출발하여 오른쪽 아래 (n, m)에 도착하는 경우의 수를 구하는 문제.
   (1 ≤ n, m ≤ 1,000)

5. 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다.

6. DP 유형의 문제

🖥 소스 코드

from sys import stdin

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

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]) % (int(1e9) + 7)

print(dp[n][m])

🔖 예제 및 실행결과

예제

4 5

실행결과

129

⌨️ 문제 풀이

1. 이번 문제는 다이나믹 프로그래밍의 기본형이라고 생각하고 풀이해보았다.

2. 문제에서 요구하는 것은 (1, 1)부터 (N, M)까지 도달하는 경우의 수를 구하는 것이다.

3. (N * M) 크기의 2차원 배열을 DP 라고 한다면, 이 문제에서 바라는 값은 DP[N][M]에 있을 것이다.

4. (3)번에서 구하려는 DP[N][M] 의 값은 각각 DP[N-1][M], DP[N][M-1], DP[N-1][M-1] 의 합으로 표현할 수 있다.
   DP[N-1][M] 또한 DP[N-2][M], DP[N-1][M-1], DP[N-2][M-2] 의 합으로 표현할 수 있다.

5. 이에 따라서 점화식은 DP[i][j] = (DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) 이다.

6. 이를 int(1e9) + 7 로 나눈 나머지를 dp에 저장한다.