[10164] 격자상의 경로

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

10164번: 격자상의 경로

<문제>

(1,1)에서 (N,M)까지 가는 경로의 경우의 수를 출력한다.

이때, 중간에 무조건 거쳐가야 하는 지점이 1개 존재할 수 있고, 아래쪽이나 오른쪽으로만 움직일 수 있다.

 

우선, 이동방향이 아래쪽 혹은 오른쪽으로 고정된 관계로, 모든 경우의 수는 최단경로이다.

일반적으로 상하좌우 모두 이동이 가능하다면,

최단경로가 P이고 왼쪽 혹은 위쪽으로 이동한 횟수가 Q일때, 이동횟수는 P + (2 * Q)가 된다.

이문제는 Q == 0 을 항상 보장하는 문제라고 할 수 있겠다.

 

N과 M이 매우 작은 관계로( N,M<=15 ) 조합을 이용해서 간단히 해결할 수 있다.

(1,1)에서 (N,M)까지 갈 수 있는 경우의 수는 (N + M - 2)C(N - 1)이다.

N + M - 2가 의미하는 것은 총 이동해야 하는 횟수를 의미하고,

N - 1이 의미하는 것은 그중 아래쪽으로 이동해야 하는 횟수를 의미한다.

전체 횟수에서 아래쪽으로 이동할 턴이 정해지면, 이외의 턴은 전부 오른쪽으로 이동하면 되는것이다.

N과 M이 unsigned long long이나 long long을 약간 벗어난다면, combination을 약분하며 진행해도 된다.

다만, 이문제는 약분하지 않고도 충분히 커버할 수 있을정도로 N과 M이 작다.

 

<소스코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
 
ll combination(int n, int r) {
    if (n <= 1 || r == 0)return 1;
    ll res = 1;
    int i, j;
    for (i = n, j = 1; j <= r; j++) {
        res *= i;
        i--;
    }
    for (i = r; i >= 2; i--) {
        res /= i;
    }
    return res;
}
int main(void) {
    int n, m, k, x = 0, y = 0;
    scanf("%d %d %d", &n, &m, &k);
    if (k > 0) {
        x = (k - 1) / m;
        y = (k - 1) % m;
    }
    printf("%lld", combination(x + y, y) * combination(m + n - (x + y) - 2, m - y - 1));
    return 0;
}