#include <stdio.h>

int D[40][40];
int x, y;
int N, M, K, ans;

int way(int fx, int fy){
    if(fx == 1 || fy == 1) return 1;
    if(fy > N || fx > M) return 0;
    if(D[fx][fy]) return D[fx][fy];
    return D[fx][fy] = way(fx - 1, fy) + way(fx, fy - 1);
}

int main()
{
    scanf("%d %d %d", &N, &M, &K);
    if(K == 0) ans = way(M, N);
    else {
        double tmp;
        tmp = (double)K / (double)M;
        if(tmp - (int)(K / M) > 0) y = (K / M) + 1;
        else y = K / M;
        x = K - M * (y - 1);
        ans = way(x, y) * way(M - x + 1, N - y + 1);
    }
    printf("%d", ans);
    return 0;
}
이게 제대로 된 답인데... 그것도 맞지 않나요...?

아래의 프로그램중

 if(D[fx][fy]) return D[fx][fy];

이 부분을 보면 해당 위치에 이미 호출해서 값이 구해진 기록이 있으면 다시 호출하지 않습니다.

하지만 위의 코드는 같은 위치를 계속 반복해서 호출을 하게 되므로 스택메모리 공간이 부족하게 됩니다.