JUMPGAME문제 질문입니다!

  • Swiiiiis
    Swiiiiis

    아래 코드에서 주석을 안한부분으로 제출했을 때 시간초과가 되질않았지만, 아래부분으로 했을 경우 시간초과가 되었습니다. 이 두 개의 차이점이 궁금합니다.!

        return ret = (jump(y + jumpSize, x) || jump(y, x + jumpSize));
/*
if (jump(y + jumpSize, x) == 1 || jump(y, x + jumpSize) == 1) {
    return 1;
}
else return 0;
*/

    아래는 코드 전체입니다.

    #include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int Board[100][100];
int Boardsize;
int cache[100][100];
int jump(int y, int x)
{   if ((y >= Boardsize) || (x >= Boardsize)) {
        return 0;
    }
    if ((y == Boardsize - 1) && (x == Boardsize - 1)) {
        return 1;
    }
    //메모이제이션
    int &ret = cache[y][x];
    if (ret != -1) return ret;
        int jumpSize = Board[y][x];
        return ret = (jump(y + jumpSize, x) || jump(y, x + jumpSize));
    /*
    if (jump(y + jumpSize, x) == 1 || jump(y, x + jumpSize) == 1) {
        return 1;
    }
    else return 0;
    */
}int main()
{   int testcases;
    cin >> testcases;
    while(testcases--)
    {
        memset(cache, -1, sizeof(cache));
        cin >> Boardsize;
        for (int y = 0; y < Boardsize; y++)
        {
            for (int x = 0; x < Boardsize; x++) {
                cin >> Board[y][x];
            }
        }
        int result = jump(0, 0);
        if (result == 1) cout << "YES" << endl;
        else cout << "NO"<<endl;
    }
}~~~

    8년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.