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

IT/Python

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

joseph24 2023. 8. 24. 21:12

728x90

(1,1)에서 (n,m)까지 →, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 떄, 경우의 수

문제
안녕하세요~ 저는 오늘 다이나믹 프로그래밍 $($ 동적 계획법 $)$ 을 설명하기 위해 등장한 욱제예요! 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하답니다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 $($ = 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션 한다고 해요 $)$ 반복되는 똑같은 연산 횟수를 줄이는 거예요.

예를 들어서, 5번째 피보나치 수열을 구하는 F $($ 5 $)$ 의 동작 과정을 살펴볼게요.

같은 함수가 불필요하게 많이 호출되는 것을 볼 수 있죠? F $($ 2 $)$ 와 F $($ 3 $)$ 을 미리 구해놓고 F $($ 4 $)$ 를 구할 땐 미리 구해둔 F $($ 2 $)$ 와 F $($ 3 $)$ 의 값을 이용하면 불필요한 호출을 줄일 수 있어요. 조금 엄밀하게 이야기 해볼게요. 수학적으로 피보나치 수열은 $F (n) = F (n - 1) + F (n - 2)$ 로 정의할 수 있죠? 이 식을 세우는 과정을 점화식을 세운다고 해요. 문제의 조건에 맞는 수식을 만들고 그 수식을 그대로 코드에 옮기면 아주 쉽게 다이나믹을 구현할 수 있어요.

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

어때요? 다이나믹 어렵지 않죠? 이제 문제를 풀어볼게요!

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

시작!

입력
n과 m이 주어진다. $($ 1 ≤ n, m ≤ 1,000 $)$

출력
$($ 1, 1 $)$ 에서 $($ n, m $)$ 에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007 $(= 10^{9} + 7)$ 로 나눈 나머지를 출력한다.

https://www.acmicpc.net/problem/14494

첫 번째 열은 ↓로만 이동 가능하고 첫 번째 행은 →로만 이동 가능해 모두 경우의 수가 1가지 입니다.

그래서 1로 채우고, 나머지 장소는 →, ↓, ↘로 이동 가능하므로 도착지의 좌, 상, 왼쪽 위 대각선 이 세가지의 경우의 수를 더한 값이 됩니다.

nxm 크기의 2차원 리스트를 만들어 위의 방식대로 이중 for문으로 값을 채워나가면 최종 목적지로 가는 경우의 수를 구할 수 있습니다.

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

for i in range(n):
    for j in range(m):
        if  i == 0 or j == 0:
            D[i][j] = 1
        else:
            D[i][j] = (D[i-1][j] + D[i-1][j-1] + D[i][j-1])%(1000000007)

print(D[n-1][m-1])

import sys
n, m = map(int, sys.stdin.readline().split())
# 가로 세로에 한 칸씩 더 늘려서 if 문 없이 답을 구할 수도 있습니다.
D = [[0]*(m+1) for _ in range(n+1)]
D[0][0] = 1
for i in range(1,n+1):
    for j in range(1,m+1):
        D[i][j] = (D[i-1][j] + D[i-1][j-1] + D[i][j-1])%(10**9+7)
print(D[-1][-1])

예제 입력 1

3 2

예제 출력 1

예제 입력 2

4 5

예제 출력 2

예제 입력 3

1000 1000

예제 출력 3

910657857