[BOJ] 1513 - 경로 찾기

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

BOJ - 경로 찾기

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold II

시간 제한: 2초

메모리 제한: 128MB

 

문제

세준이는 크기가 N*M인 직사각형 도시에 살고 있다. 또, 세준이의 집은 (1, 1)에 있고, 학원은 (N, M)에 있고, 오락실이 C개 있다.

세준이의 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동할 수 있다. 오락실을 방문할 때는 규칙이 하나 있는데, 오락실 번호가 증가하는 순서대로 가야한다는 것이다. 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안 되고, 2번 오락실을 가려면, 그 전에 아무 오락실도 가지 않거나, 1번 오락실을 방문했을 때만 가능하다.

세준이는 오락실을 K번 방문해서 학원에서 도착하는 경로의 경우의 수가 궁금해지기 시작했다. 오락실을 0개 방문했을 때부터, C개 방문했을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N M C가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, C는 50보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 C개의 줄에 1번 오락실부터 C번 오락실까지 위치가 차례대로 주어진다. 오락실의 위치가 중복되는 경우는 없지만, 오락실의 위치가 (1,1) 또는 (N,M)일 수도 있다.

 

출력

첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다.

 

풀이

dp[row][col][오락실 방문횟수][지금까지의 최대 오락실번호] = 경우의 수

로 두고 문제를 풀면 된다.

 

만약 이번칸에 오락실이 있다면, 이전 칸으로부터 오락실 방문횟수가 1 낮고, 최대 오락실번호가 낮은 경우의 수들을 누적하면 되는 것이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1'000'007;

int n, m, c;

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> c;
    vector<vector<int>> mat(n, vector<int>(m));
    vector<vector<vector<vector<int>>>> dp(
        n, vector<vector<vector<int>>>(
               m, vector<vector<int>>(
                      51, vector<int>(51))));  // r, c, count, maxNum;

    for (int i = 1; i <= c; i++) {
        int r, c;
        cin >> r >> c;
        mat[r - 1][c - 1] = i;
    }

    if (mat[0][0] != 0)
        dp[0][0][1][mat[0][0]] = 1;
    else
        dp[0][0][0][0] = 1;

    for (int i = 1; i < n; i++) {
        if (mat[i][0] > 0) {
            int gameNo = mat[i][0];
            for (int k = 1; k <= c; k++) {
                for (int l = 0; l < gameNo; l++) {
                    dp[i][0][k][gameNo] =
                        (dp[i][0][k][gameNo] + dp[i - 1][0][k - 1][l]) % MOD;
                }
            }
        } else {
            for (int k = 0; k <= c; k++) {
                for (int l = 0; l <= 50; l++) {
                    dp[i][0][k][l] =
                        (dp[i][0][k][l] + dp[i - 1][0][k][l]) % MOD;
                }
            }
        }
    }
    for (int j = 1; j < m; j++) {
        if (mat[0][j] > 0) {
            int gameNo = mat[0][j];
            for (int k = 1; k <= c; k++) {
                for (int l = 0; l < gameNo; l++) {
                    dp[0][j][k][gameNo] =
                        (dp[0][j][k][gameNo] + dp[0][j - 1][k - 1][l]) % MOD;
                }
            }
        } else {
            for (int k = 0; k <= c; k++) {
                for (int l = 0; l <= 50; l++) {
                    dp[0][j][k][l] =
                        (dp[0][j][k][l] + dp[0][j - 1][k][l]) % MOD;
                }
            }
        }
    }

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (mat[i][j] > 0) {
                int gameNo = mat[i][j];
                for (int k = 1; k <= c; k++) {
                    for (int l = 0; l < gameNo; l++) {
                        dp[i][j][k][gameNo] =
                            (dp[i][j][k][gameNo] + dp[i - 1][j][k - 1][l]) %
                            MOD;
                        dp[i][j][k][gameNo] =
                            (dp[i][j][k][gameNo] + dp[i][j - 1][k - 1][l]) %
                            MOD;
                    }
                }
            } else {
                for (int k = 0; k <= c; k++) {
                    for (int l = 0; l <= 50; l++) {
                        dp[i][j][k][l] =
                            (dp[i][j][k][l] + dp[i - 1][j][k][l]) % MOD;
                        dp[i][j][k][l] =
                            (dp[i][j][k][l] + dp[i][j - 1][k][l]) % MOD;
                    }
                }
            }
        }
    }

    for (int i = 0; i <= c; i++) {
        int ans = 0;
        for (int j = 0; j <= 50; j++) {
            ans = (ans + dp[n - 1][m - 1][i][j]) % MOD;
        }
        cout << ans << " ";
    }
    cout << "\n";

    return 0;
}