10164번: 격자상의 경로

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


$O(n+m)$

(0,0) 에서 (x,y)까지 한 칸씩 좌표값이 증가하게 가는 경우의 수는 (x+y)Cx임을 이용한다.

#include<cstdio>
int n, m, k, tx, ty;
long long dp[31][31];
int c(int x, int y) {
    int r = 1;
    for (int i = 1; i <= y; i++) r = r*(x - i + 1) / i;
    return r;
}
int main() {
    scanf("%d %d %d", &n, &m, &k);
    if (k) tx = (k - 1) / m, ty = (k - 1) % m;
    printf("%d", c(tx + ty, ty)*c(n + m - 2 - tx - ty, n - 1 - tx));
    return 0;
}