[백준/알고리즘] #10164: 격자상의 경로 [파이썬(python)/수학/DP]

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

10164번: 격자상의 경로

32점을 받아서 부분성공했다...

100점을 어떻게 해야 받는건지 모르겠다..

점화식 세운다고 굿노트 한장을 꽉 채워서 계속 적어보았는데..

난 아무래도 돌머리인거같다 허헣 ^___^

#10164_격자상의경로
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
#N:행, M:열 (상하반전)
def dp_search(y,x):
    dp = [[0 for _ in range(x+1)] for _ in range(y+1)]

    for i in range(1, y+1):
        for j in range(1, x+1):
            if i==1 and j==1:
                dp[i][j]=1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[y][x]

if K==0:
    print(dp_search(N,M))
else:
    #K의 (y,x)좌표 구하기
    k_y = (K+1) // (M-1)
    #k_x = K % M
    k_x = K - (k_y-1)*M
    #print(k_y, k_x)
    k_n = N - (k_y - 1)
    k_m = M - (k_x - 1)
    #print(k_n, k_m)
    route_a = dp_search(k_y, k_x)
    route_b = dp_search(k_n, k_m)

    print(route_a * route_b)