[BOJ] 백준 10164 격자상의 경로 Python

#10164 격자상의 경로
import sys
import math
input = sys.stdin.readline
A,B,K = map(int,input().split())

if K == 0:
    print(math.comb(A+B-2,B-1))
else:
    x = (K-1) // B
    y = (K-1) % B 
    a = math.comb(x+y,y)
    b = math.comb(A+B-x-y-2,B-y-1)
    print(a*b)

 

격자상의 경로를 조합 (Combination)을 이용하여 구하는 방식입니다.

마커가 단 하나기에 쉽게 풀립니다. 마커 다수의 경우에는 분기를 나누어 풀거나,
혹은 수학적 지식을 사용하지 않고 풀어야 할 것 같습니다.

예를 들어 DP라던가? 2차원 배열을 가지고 생각해야할 것 같습니다.