인프런 커뮤니티 질문&답변

답변감사합니다 선생님께서 올려주신 코드를 보면

int main(){

fastIO();

memset(dp, -1, sizeof(dp));

cin >> n >> m >> c;

for(int i = 1; i <= c; i++){

cin >> y >> x;

a[y][x] = i;

}

for(int i = 0; i <= c; i++){

cout << go(1, 1, i, 0) << " ";

}

return 0;

}
위 코드에서 dp를 한번만 초기화 시키는데 선생님께서 올려주신 코드는 dp를 한번만 초기화 해도 되는 이유가 궁금합니다

안녕하세요 ㅎㅎ

크리스마스에 답변 다는 강사... 큰돌입니다. 하하..

크리스마스땐 또 알고리즘 아니겠습니까?

제가 설명을 좀 혼란스럽게 드린 것 같습니다 ㅠ 저답변은 이렇게 수정하도록 하겠습니다.

수강생님 코드 기준 : 매번 초기화를 해야 -> 왜? target 다르게 해서 go함수할 때 그 이전 go가 다음 go 에 잘못된 영향을 미침 -> 매번 초기화 안하면 DP가 올바르게 안쌓임.

수강생님과 저의 코드의 차이는

이부분에 있는데요.

1. cnt + 1

    if (game[y][x] > idx)
        ret = (go(y + 1, x, game[y][x], cnt + 1) + go(y, x + 1, game[y][x], cnt + 1)) % divn;

이렇게 + 1을 하면서 증가를 시키며 재귀함수를 작동시키죠? 그러면서 DP를 쌓구요. bottom-up이죠?

그리고...

2. 그 + 1은 마지막 기저사례에도 연관이 되어있구요. (target과 비교해서...)

    if (y == n && x == m) {
        if (cnt == target && game[y][x] == 0) { return 1;}
        if (cnt == target - 1 && game[y][x] > idx) { return 1;}
        return 0;
    }

수강생님 코드는

0을 만들기 위해 1 2 3 4 를 호출해버립니다.

이거는 디버깅을 하면 알 수 있는데요. (지금 보시면.. 1 1 1로 뜨는 것을 볼 수 있습니다. 0까지만 잘 되요.)

예제 1기준.

1 : 1 : 0 : 0
-1
2 : 1 : 0 : 0
-1
3 : 1 : 0 : 0
-1
3 : 2 : 2 : 1
-1
2 : 2 : 1 : 1
-1
3 : 2 : 2 : 2
-1
2 : 3 : 1 : 1
-1
1 : 2 : 0 : 0
-1
2 : 2 : 1 : 1
0
1 : 3 : 0 : 0
-1
2 : 3 : 0 : 0
-1
RET : 1
1 : 1 : 0 : 0
1
RET : 1
1 : 1 : 0 : 0
1
RET : 1

이렇게 보면 target = 0이니까 0까지만 확인할 것 같은데

    if (y == n && x == m) {
        if ((cnt == target && game[y][x] == 0) || (cnt == target - 1 && game[y][x] > idx))
            return 1;
        return 0;
    }

코드를 보면 n, m 까지 와서 return .. 하기 때문에

int go(int y, int x, int idx, int cnt) {

이 cnt라는 부분이 + 1 + 1... 을 어느정도 하다가 DP가 만들어지게 됩니다.

그렇게 되면

DP[0]을 만들 때 DP[2]를 만드는 격이고.

DP[2]를 만들 때 그 만들어진 DP[2]를 참조하게 되버립니다.

이 때 DP[0]은 문제가 없지만 여기서 만들어지는 DP[2]는 문제가 있습니다.

오락실 0개를 방문했을 때 만들어지는 DP[2]라 아예 이상한 DP라고 보면 됩니다.

물론 이게 독립적으로 memset을 해서 매번 초기화하면 상관없지만 ...

그렇지 않으면 문제가 생기는 것이죠.

제코드

제코드를 간단히 설명하면

0

1 0

2 1 0

3 2 1 0 ...

이렇게 됩니다. 0을 만들 때는 그 0에 한정되어 DP를 만듭니다. 1을 만들 때는 그 이전에 DP를 사용하나 1을 만들 때 2, 3, 4... 의 DP를 만들지는 않습니다.

디버깅 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 51;
const int MOD = 1000007;
int dp[MAXN][MAXN][MAXN][MAXN];
int game[MAXN][MAXN];
int n, m, c, target;

int go(int y, int x, int idx, int cnt) {
    if (y > n || x > m) return 0; // Corrected boundary conditions
    if (y == n && x == m) {
        if ((cnt == target && game[y][x] == 0) || (cnt == target - 1 && game[y][x] > idx))
            return 1;
        return 0;
    }
    int &ret = dp[y][x][idx][cnt];
    cout << y << " : " << x << " : " << idx << " : " << cnt << "\n";
    cout << ret << "\n";
    if (ret != -1) return ret;

    ret = 0;
    if (y < n && (game[y + 1][x] > idx || game[y + 1][x] == 0))
        ret = (ret + go(y + 1, x, max(idx, game[y + 1][x]), game[y + 1][x] > idx ? cnt + 1 : cnt)) % MOD;
    if (x < m && (game[y][x + 1] > idx || game[y][x + 1] == 0))
        ret = (ret + go(y, x + 1, max(idx, game[y][x + 1]), game[y][x + 1] > idx ? cnt + 1 : cnt)) % MOD;

    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> c;
    int x, y;
    for (int i = 1; i <= c; ++i) {
        cin >> y >> x;
        game[y][x] = i;
    }
 
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i <= c; ++i) {
        target = i; 
        int ret = go(1, 1, 0, 0);
        cout << "RET : " << ret << '\n'; 
    }
    cout << endl;

    return 0;
}

즐거운 크리스마스 보내시길 바랍니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.