[BOJ 10164] 격자상의 경로

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

10164번: 격자상의 경로

 

이번에 다룰 문제도, 다이나믹 프로그래밍 문제입니다.

 

 

 

 

꼭 지나야 하는 지점을 통해서, 최종 목적지(N, M)까지 도달하는 경우의 수를 찾아야 합니다.

 

 

 

 

위의 조건을 만족하는 경우의 수를 찾기 이전에, 임의의 (i, j)의 지점에 도달하는 문제를 해결해봅시다.

 

 

 

 

다이나믹 프로그래밍의 본질은, 큰 문제를 해결하기 위해서, 작은 문제들의 해결을 이용하는 것입니다.

 

 

 

 

임의의 (i, j)에 도달하는 경우의 수는,

 

 

 

 

DP[i][j] = DP[i - 1][j] + DP[i][j - 1]

 

 

 

 

위의 식으로 손쉽게 정의할 수 있다.

 

 

 

 

하지만, 이 문제에는 특정 지점을 경로해야 한다. 

 

 

 

 

그렇다면 정답은, 특정 지점을 경로하는 경우의 수 * 특정 지점에서 목적지까지 경우의 수의 곱의 형태를 이룰 것이다.

 

 

 

 

이걸 식으로 표현해야 한다.

 

 

 

 

해설코드(C++).

 

#include <iostream>

using namespace std;

 

int N, M, K;

int dp[16][16];

int main() {

    // your code goes here

    cin >> N >> M >> K;

    for(int i = 1; i <= M; i++)

        dp[1][i] = 1;

        

    for(int i = 1; i <= N; i++)

        dp[i][1] = 1;

    

    for(int i = 2; i <= N; i++){

        for(int j = 2; j <= M; j++){

            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

        }

    }

    

    if(K == 0){

        cout << dp[N][M] << endl;

        return 0;

    }

    

    int r, c;

    if(K % M == 0){

        r = K / M;

        c = M;

    }

    else{

        r = (K / M) + 1;

        c = K % M;

    }

    

    cout << dp[r][c] * dp[1 + (N - r)][1 + (M - c)] << endl;

    return 0;

}