글 읽기 - 어디에서 틀린거죠??ㅠ

ajax0615 7년 전 0

for문으로 풀면 잘 풀리는데,

재귀로 리턴값 캐싱해서 풀었더니 답은 잘 나오는데 틀렸다고 나오네요.

코드상에서 ㅇㅓ느 부분이 틀린건가요??

#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
vector<vector<int> > arr;
vector<vector<ll> > cache;
int endX, endY;

ll calculate(int i, int j) {
    if (i > endX || j > endY) return 0;

    ll &ret = cache[i][j];
    if (-1 != ret) return 0;

    int here = arr[i][j];
    int down = calculate(i + 1, j);
    int right = calculate(i, j + 1);
    ret = here + down + right;
    return ret;
}

int main() {
    int N, M;
    scanf("%d %d\n", &N, &M);
    arr.assign(N, vector<int> (M, 0));
    for (int i = 0; i < arr.size(); ++i) {
        for (int j = 0; j < arr[0].size(); ++j) {
            scanf("%d", &arr[i][j]);
        }
    }

    int numOfTestCase;
    scanf("%d\n", &numOfTestCase);
    int startX, startY;
    for (int i = 0; i < numOfTestCase; ++i) {
        cache.assign(N, vector<ll> (M, -1));
        scanf("%d %d %d %d", &startX, &startY, &endX, &endY);
        --endX; --endY;
        printf("%lld\n", calculate(startX - 1, startY - 1));
    }

    return 0;
}

yukariko 7년 전 1

같은 startX와 startY를 가지고 있어도 endX, endY가 다르면 답이 달라질 수 있으니 캐싱이 제대로 되지 않습니다.

ajax0615 7년 전 0

@yukariko

그럼 다음과 같은 경우에 캐싱을 하려면 캐시 배열에 [startX][startY][endX][endY] 값들을 캐싱해야 하잖아요.

그런데 입력으로 주어지는 범위가 [300][300][300][300] 일 경우, 메모리가 초과할텐데 적절하게 캐싱하는 방법 없을까요?

메모이제이션으로 해결할 수 있는 바법은 없나요?

for문으로 해결해야하는 문제인가요?

yukariko 7년 전 0

시작점을 1,1 같은 좌표로 고정시키고 캐싱을 하면 간단한연산으로 답을 구할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디에서 틀린거죠??ㅠ

ajax0615 7년 전 0

yukariko 7년 전 1

ajax0615 7년 전 0

yukariko 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말