10164번 격자상의 경로

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

아래와 비슷한 문제 풀이법이다.(프로그래머스의 '등굣길' 문제)

따라서, 아래의 블로그 글만 보면 되니, 풀이는 생략.

굳이 언급하자면,

거쳐가려면, 두 경우의 수를 곱해야 한다.(곱사건)

https://hsdevelopment.tistory.com/350?category=1048260

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 18
 
int dp[Max][Max];
 
int Count(int sy, int sx, int ey, int ex)
{
    memset(dp, 0, sizeof(dp));
 
    for (int i = 0; i < Max; i++) {
        dp[1][i] = dp[i][1] = 1;
    }
 
    ey = ey - sy + 1;
    ex = ex - sx + 1;
 
    for (int i = 2; i <= ey; i++) {
        for (int j = 2; j <= ex; j++) {
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
        }
    }
 
    //printf("ey = %d, ex = %d, dp[%d][%d] = %d\n", ey, ex, ey, ex, dp[ey][ex]);
 
    return dp[ey][ex];
}
 
int main()
{
    cin.tie(0);
 
    int r, c, k;
 
    scanf("%d %d %d", &r, &c, &k);
 
    if (k) {
        int num = 0, y = r, x = c;
        bool stop = false;
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                if (++num == k) {
                    y = i;
                    x = j;
                    stop = true;
                    break;
                }
            }
            if (stop) break;
        }
 
        printf("%d\n", Count(1, 1, y, x) * Count(y, x, r, c));
    }
    else {
        printf("%d\n", Count(1, 1, r, c));
    }
 
    return 0;
}