[백준] 1890번 점프 C++ 코드

코드

#include <cstdio>

using namespace std;
typedef long long ll;

ll n, a[103][103], dp[103][103];

ll go(int x, int y) {
    if(x >= n || y >= n) return 0; // 범위를 벗어난 경우
    if(x == n - 1 && y == n - 1) {
        return 1;
    }
    if(a[x][y] == 0) return 0; // (n-1,n-1)이 아닐때 0이 나오면 함수 종료
    if(dp[x][y] != -1) return dp[x][y]; // 메모이제이션
    
    // 오른쪽으로 가는 경우 + 아래로 가는 경우
    dp[x][y] = go(x + a[x][y], y) + go(x, y + a[x][y]);
    return dp[x][y];
}

int main() {
    scanf("%lld", &n);
    // algorithm 헤더의 fill함수로 대체 가능
    for(int i = 0; i < 103; i++) {
        for(int j = 0; j < 103; j++) {
            dp[i][j] = -1;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%lld", &a[i][j]);
        }
    }
    printf("%lld\n", go(0,0));
    return 0;
}

오른쪽으로 가는 경우와, 아래쪽으로 가는 경우를 모두 찾아주려고 했다. 반복되는 연산이 있는 것 같아서 dp가 생각났고, 이를 적용해주었다. go함수 중간 부분에 if(a[x][y] == 0) return 0; 를 빼면 메모리 초과가 난다. 이 케이스는 더 이상 진행할 수 없기 때문에 해당 지점에서 재귀 호출을 하지 않아야 한다. (n-1,n-1)에서 0인 경우를 위에서 이미 처리했기 때문에 결과에는 영향을 미치지 않는다. 오른쪽으로 간 경우의 수와 아래로 간 경우의 수를 더해주면 답이 나온다.