백준 1513 - 경로 찾기

icpc.me/1513

 

제약이 까다로워 애를 먹었던 dp 문제이다.

 

오락실의 방문 순서는 순증가여야 한다는 점과 오락실은 출발점과 도착점에도 존재할 수 있다는 것이 문제를 어렵게 만든다.

 

다만 도시의 크기는 50 * 50이기 때문에 메모리를 넉넉하게 사용할 수 있다. 제약을 고려하여 사차원 테이블에 다음 점화식을 세울 수 있다.

 

$f(row, \, column, \, last, \, cnt) = $ row 행 column 열에서 마지막으로 방문한 오락실의 순서 번호가 last일 때 남은 오락실 방문 가능 횟수 cnt

 

map을 사용하여 오락실의 순서 번호를 저장한 뒤, 점화식으로 탑 다운 dp를 돌리면서 cnt번의 방문으로 학교에 도착할 수 없거나 방문했었던 오락실보다 순서 번호가 더 낮은 오락실에 방문하는 경우를 걸러주면 효과적으로 답을 구할 수 있다.

 

전체 코드

#include <bits/stdc++.h>
 
#define mod 1000007
 
using namespace std;
using pii = pair<int, int>;
 
int n, m, v;
int dp[51][51][51][51];
map<pii, int> funidx;
 
int memo(int r, int c, int last, int cnt);
 
int main()
{
    memset(dp, -1, sizeof dp);
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n >> m >> v;
 
    for (int i = 1; i <= v; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        funidx[{a, b}] = i;
    }
 
    for (int i = 0; i <= v; ++i)
        cout << memo(1, 1, 0, i) << ' ';
}
 
int memo(int r, int c, int last, int cnt)
{
    int &ret = dp[r][c][last][cnt];
 
    if (ret != -1)
        return ret;
 
    ret = 0;
 
    if (funidx.count({r, c}))
    {
        if (last > funidx[{r, c}])
            return ret;
 
        if (r == n && c == m && cnt == 1)
            ret = 1;
 
        if (r < n && cnt > 0)
            ret = (ret + memo(r + 1, c, funidx[{r, c}], cnt - 1)) % mod;
        if (c < m && cnt > 0)
            ret = (ret + memo(r, c + 1, funidx[{r, c}], cnt - 1)) % mod;
    }
    else
    {
        if (r == n && c == m && !cnt)
            ret = 1;
 
        if (r < n)
            ret = (ret + memo(r + 1, c, last, cnt)) % mod;
        if (c < m)
            ret = (ret + memo(r, c + 1, last, cnt)) % mod;
    }
 
    return ret;
}