[백준_10164] 격자상의 경로 python

초등학교때 했던 길찾기 문제를 활용한 dp문제였다.

신나서 dp설계하고 점화식 세웠는데 

어이가 없다 ㅋㅋ

,,, 쨋든 내가 생각한 방법은 다음과 같다.

# 입력

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

# dp 설계

dp = [

　[0] * (m + 1) for _ in range(n + 1)

]

# 초기값 설정

dp[1][1] = 1

# k == 0인 경우

if k == 0:

　for i in range(2, m + 1):

　　dp[1][i] = 1

　for j in range(2, n + 1):

　　dp[j][1] = 1

　for i in range(2, n + 1):

　　for j in range(2, m + 1):

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

　print(dp[n][m])

# k != 0 인 경우

else:

　# k 좌표 찾기

　p = k // m + 1

　q = k % m

　# 첫 번째 dp

　for i in range(2, p + 1):

　　dp[i][1] = 1

　for j in range(2, q + 1):

　　dp[1][j] = 1

　for i in range(2, p + 1):

　　for j in range(2, q + 1):

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

 

　# 두 번째 dp

　for i in range(p + 1, n + 1):

　　dp[i][q] = dp[p][q]

　for j in range(q + 1, m + 1):

　　dp[p][j] = dp[p][q]

　for i in range(p + 1, n + 1):

　　for j in range(q + 1, m + 1):

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

　print(dp[n][m])