[백준][C++] 10164: 격자상의 경로

문제

10164번: 격자상의 경로

풀이

수학, 다이나믹 프로그래밍, 조합론

 

격자상에서 각 칸에 도달할 수 있는 경로의 경우의 수는 다음과 같다.

1	1	1	1	1
1	2	3	4	5
1	3	6	10	15

0번 행과 0번 열은 모두 한가지의 방법만 존재한다. (x, y) 칸에 도달할 수 있는 경로의 수는 (x - 1, y) 칸과 (x, y - 1) 칸에 올 수 있는 경우의 수의 합이다. 

 

중간 경로 K를 지나면서 마지막 칸에 도달하는 경우의 수는 (1번 칸에서 K칸까지의 경로의 수) * (K칸에서 마지막 칸까지의 경로의 수)이다. K의 (x, y) 좌표는 다음과 같이 나타낼 수 있다. 

// 중간 경로 K의 (x, y) 좌표는 다음과 같이 나타낼 수 있다.
int K_x = (K - 1) / M;
int K_y = (K - 1) % M;

K칸을 1번칸이라고 생각하면 마지막 칸까지의 경로의 수는 다음과 같이 나타낼 수 있다. 

// K에서 마지막 칸까지의 경로
int dest_count = cache[N - K_x - 1][M - K_y - 1];

 

K가 0이라면 마지막 칸까지의 경로의 수를 바로 출력한다.

 

코드

#include <iostream>

using namespace std;

int cache[16][16];

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i < M; ++i)
    {
        cache[0][i] = 1;
    }
    for (int i = 0; i < N; ++i)
    {
        cache[i][0] = 1;
    }

    // (x, y)칸에 올 수 있는 경우의 수는 (x - 1, y)칸과 (x, y - 1)칸에 올 수 있는 경우의 수의 합이다.
    for (int i = 1; i < N; ++i)
    {
        for (int j = 1; j < M; ++j)
        {
            cache[i][j] = cache[i - 1][j] + cache[i][j - 1];
        }
    }

    if (K == 0)
    {
        cout << cache[N - 1][M - 1];
    }
    else
    {
        // 중간 경로 K의 (x, y) 좌표는 다음과 같이 나타낼 수 있다.
        int K_x = (K - 1) / M;
        int K_y = (K - 1) % M;

        // K에서 마지막 칸까지의 경로
        int K_count = cache[K_x][K_y];
        int dest_count = cache[N - K_x - 1][M - K_y - 1];

        // K까지의 경로와 K에서 마지막 칸 까지의 경로의 곱을 출력
        cout << K_count * dest_count;
    }

    return 0;
}