[백준] 10164 격자상의 경로

10164번: 격자상의 경로

 

www.acmicpc.net

풀이

등굣길문제와 유사하게 해결하였다. 출발지에서 꼭 들려야하는 지점까지 가는 방법의 수와 꼭 들려야하는 곳에서 N X M 번재 지점까지 가는 방법의 수를 구해서 곱해주면 모든 경로의 개수가 된다.

코드

C++

#include <iostream>
#include <vector>
using namespace std;

int n, m, k, r, c;
vector<vector<int>> dp1, dp2;

int main() {
    cin >> n >> m >> k;
    dp1 = vector<vector<int>>(n, vector<int>(m, 1));
    dp2 = vector<vector<int>>(n, vector<int>(m, 1));

    if (k == 0) {
        r = n - 1;
        c = m - 1;
    }
    else {
        if (k % m == 0) r = k / m - 1;
        else r = k / m;
        c = k - 1 - m * r;
    }

    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            dp1[i][j] = dp1[i - 1][j] + dp1[i][j - 1];

    for (int i = r + 1; i < n; i++)
        for (int j = c + 1; j < m; j++)
            dp2[i][j] = dp2[i - 1][j] + dp2[i][j - 1];
    cout << dp1[r][c] * dp2[n - 1][m - 1] << '\n';
    return 0;
}

Kotlin

fun main() {
    val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
    val dp1 = Array(n) { Array(m) { 1 } }
    val dp2 = Array(n) { Array(m) { 1 } }
    val r: Int
    val c: Int
    if (k == 0) {
        r = n - 1
        c = m - 1
    } else {
        r = if (k % m == 0) k / m - 1 else k / m
        c = k - 1 - r * m
    }
    for (j in 1..c)
        for (i in 1..r)
            dp1[i][j] = dp1[i][j - 1] + dp1[i - 1][j]

    for (j in c + 1 until m)
        for (i in r + 1 until n)
            dp2[i][j] = dp2[i][j - 1] + dp2[i - 1][j]
    println(dp1[r][c] * dp2[n - 1][m - 1])
}