BOJ 10164 격자상의 경로

www.acmicpc.net/problem/10164

10164번: 격자상의 경로

 

DP를 연습하던 중에 재미있는 풀이로 풀 수 있어서 가져와 봤다.

k가 존재하면 (0, 0)에서 k가 존재하는 인덱스 (i, j)까지 의 길 찾기 경우의 수 \(nCk\)로 구하고

그 k에서 (n - 1, m - 1)까지의 경우의수를 또 구하면 된다.

 

나이브하게 풀면 오버플로가 나고 dp테이블에 조합을 저장해 두고 풀어야 한다.

 

 

#include <iostream>
using namespace std;
using ll = long long;
 
ll d[31][31], n, m, k;
int a, b, cnt;
 
ll comb(int n, int k) {
    if (n == k || k == 0) return 1;
    if (d[n][k]) return d[n][k];
    return d[n][k] = comb(n - 1, k - 1) + comb(n - 1, k);
}
 
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (++cnt == k) {
                a = i, b = j; break;
            }
 
    ll x, y;
    if (k) x = comb(a + b, a);
    else x = 1;
    n = (n - 1) - a, m = (m - 1) - b;
    y = comb(n + m, n);
 
    cout << x * y << endl;
 
    return 0;
}

 

고등학교 수학 지식을 활용해서 풀어보니 재밌었다.