경로찾기

18 Sep 2018

Problem

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

Idea

d[x][y][c]: x,y에 왔을 때 총 들린 오락실 수가 c일 때의 총 경우의 수로 부분 정의

오락실이 증가하는 방향이어야 하므로 상태가 하나 더 필요

d[x][y][k][c]: x,y에 왔을 때 이전 들린 오락실이 k이고, 총 들린 오락실 수가 c일 때의 총 경우의 수로 부분 정의

// d[i][j][k][c] += d[i-1][j][k][c-1] + d[i][j-1][k][c-1];

f(x, y, k, c) =

f(x - 1, y, k, i) + f(x, y - 1, k, i) // 1 <= i <= C, if x=y is not game room

f(x - 1, y, j, i - 1) + f(x, y - 1, j, i - 1) // 1 <= i <= C, 0 <= j < game room, if x=y is game room

상향식

for (int i=0; i<=C; i++) {
    for (int k=0; k < max(C,1); k++) {
        ans[i] += d[N][M][k][i];
        ans[i] %= mod;
    }
    printf("%d ",ans[i]);
}

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        if (game[i][j] == -1) { //오락실이 아니고 하나도 안들린경우
            d[i][j][0][0] += d[i-1][j][0][0] + d[i][j-1][0][0];
            d[i][j][0][0] %= mod;
        }
        // 오락실 c개 들리는 경우
        for (int c = 1; c <= C; c++) {
            int gameNum = game[i][j];
            if (gameNum == -1) {
                // 오락실이 아니면 방문한 오락실들 확인
                for (int k = 0; k <= C; k++) {
                    d[i][j][k][c] += d[i-1][j][k][c] + d[i][j-1][k][c];
                }
            } else {
                if (c == 1) {
                    // 현위치가 오락실이고 처음방문하는 경우라면
                    // 이전 오락실은 0, 이전 방문 총 오락실 수 0
                    d[i][j][0][c] += d[i-1][j][0][0] + d[i][j-1][0][0];
                } else {
                    for (int k = 0; k < gameNum; k++) {
                        d[i][j][k][c] += d[i-1][j][k][c-1] + d[i][j-1][k][c-1];
                    }   
                }

            }
            
        }
    }
}

하향식

for (int i = 0; i <= c; i++) {
    int ans = 0;
    for (int j = 0; j <= c; j++) {
        ans = f(n, m, j, i);
    }
    sysout(ans)
}

int f(int n int m, int k, int c) {
    if (n < 1 || n > N || m < 1 || m > M) {
        return 0;
    }

    int ret = d[n][m][k][c];
    if (ret != -1) {
        return ret;
    }
    int roomNum = game[n][m];

    if (roomNum == 0) {
        // 오락실이 아니면 이전과 상태변화가 없다
        ret = f(n-1, m, k, c) + f(n, m-1, k, c);
    } else {
        if (roomNum == k) {
            for (int i = 0; i < k; i++) {
                // 이전은 k 보다 적어야된다
                ret = f(n-1, m, i, c - 1) + f(n, m-1, i, c - 1);
            }
        }

    }
    

    return r;
}