글 읽기 - c++ memset/메모이제이션 관련 질문 있습니다.

preston119 4년 전 0

메모이제이션에 관한 질문입니다. 기본적으로 memset을 안해서 배열을 사용하면 0으로 기본적으로 초기화 되는걸로 아는데 그래서 만약 result!=0 이면 result를 반환하는 식으로 했습니다. 근데 이렇게 하면 시간초과가 뜨고 주석에 있는걸로 다 고쳐서 memset을 사용해서 -1로 초기화해서 문제를 풀면 답이 맞습니다. 왜 memset을 안 이용하면 안되는지 설명해주시면 정말 감사하겠습니다!!!

#include <iostream>
#include <string>
#include <algorithm>
//#include <cstring>
#define INF 987654321

using namespace std;

int n;
string s1, s2;
int cache[1001][1001];
int f(int x, int y){
    if(x==s1.size()||y==s2.size()) return 0;
    int &result = cache[x][y];
    if(result!=0) return result; // if(result!=-1) return result;
    return result = max(f(x+1,y),max(f(x,y+1),f(x+1,y+1)+(s1[x]==s2[y])));
}

int main()
{
    cin >> s1 >> s2;
    //memset(cache,-1,sizeof(cache));
    cout << f(0,0);
    return 0;
}

lickelon 4년 전 1

memset을 사용하고 사용하지 않고의 문제가 아닌 0과 -1의 문제입니다.

15번 줄에서 이후의 결과가 이미 시행된 경우 그 결과를 반환하고자 했지만,

0으로 초기화한 경우에는 LCS가 0인지, 아직 시행되지 않은 경우인지 구분이 되지 않고 계속해서 시행하기 때문에 시간복잡도가 상승합니다.

하지만 -1로 초기화한 경우에는 LCS가 0인지, 아직 시행되지 않은 경우인지 명확하게 구분이 되므로 시간초과가 발생하지 않습니다.

preston119 4년 전 0

아 그렇군요... 그럼 이런문제는 memset으로 0이 아닌값으로 초기화하는게 필수겠군요. 감사합니다!

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

문제

문제

출처

ICPC

c++ memset/메모이제이션 관련 질문 있습니다.

preston119 4년 전 0

lickelon 4년 전 1

preston119 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말