[백준] 14494번: 다이나믹이 뭐예요? - 파이썬

🔈 문제

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

예를 들어서, 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)로 나눈 나머지를 출력한다.

 

📚 문제 해석

문제의 제목에서 언급한 것처럼 이 문제는 다이나믹 프로그램을 사용하면 되는 문제였다.
1,1 에서 오른쪽으로(x+1,y), 아래로(x,y+1), 대각선 우측하단으로(x+1,y+1) 움직이면서 (n,m)으로 갈때 갈 수 있는 경우의 수를 구하면 되는 문제이다.
이동 방향이 →, ↓, ↘ 이렇게 세가지가 가능하다. 경우의 수를 구하려면 현재 위치에서 →에서 오는 경우의 수와, ↓에서 오는 경우의 수, 그리고 ↘에서 오는 경우의 수를 모두 더하면 된다. 
아래 표와 같이 설명하겠다.

 

1 1,1	1 1,2	1 1,3	1 1,4	1 1,5	1 1,6
1 2,1	3 2,2	5 2,3	7 2,4	9 2,5	11 2,6
1 3,1	5 3,2	13 3,3	25 3,4	41 3,5	61 3,6
1 4,1	7 4,2	25 4,3	63 4,4	129 4,5	231 4,6
1 5,1	9 5,2	41 5,3	129 5,4	321 5,5	681 5,6
1 6,1	11 6,2	61 6,3	231 6,4	681 6,5	1683 6,6

 

밑에 있는 것은 좌표이고, 위에 진한 글씨는 경우의 수이다. 1,1은 1로 시작하여 다음 좌표들의 경우의 수는 (x-1,y)+(x,y-1)+(x-1,y-1)의 값으로 구한다. 그리고 dp 테이블에 저장하면 그 연산은 더 이상 안 할 수 있다. 이것이 바로 다이나믹 프로그램, 동적 계획법이다. 반복되는 연산은 하지 않는 것!!!

 

📖 풀이

풀이 해석에 적었던 내용을 그대로 코드로 바꾸면 된다. x축이 1일때와, y축이 1일때 (x-1,y)+(x,y-1)+(x-1,y-1)을 해도 indexerror가 발생하지 않게 dp 테이블은 0,0부터 만들었다.

 

💻 코드

n,m = map(int, input().split()) 
dp = [[0 for i in range(n+1)] for j in range(m+1)] # 주어진 n과m 으로 dp 테이블 생성
dp[1][1] =1# 1,1 일때 경우의 수는 1

for i in range(1, m+1):
    for j in range(1, n+1):
        dp[i][j] += dp[i-1][j] + dp[i-1][j-1] + dp[i][j-1] # (x,y) + (x-1,y-1) + (x,y-1)

print(dp[m][n]%(10**9+7)) # n,m 일 때 경우의 수%10**9+7 출력

 

🔗 문제링크 : 다이나믹이 뭐예요?

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