글 읽기 - 같은 코드같은데 시간초과가 납니다!

3038ksh 7년 전 0

둘다 메모이제이션 기법을 사용했습니다.

다만 위의 코드는 cache[x][y]가 -1일때는 결과값을 구해서 저장하는 소스고,

아래 코드는 체크배열을 따로 만들어서 ck[x][y]가 체크 되어있다면 pa[x][y]의 값을 쓰고, 없다면 구해서 저장하는 소스입니다.

방법은 똑같은거 같은데, 위에는 시간초과가 나고 아래는 통과합니다.

제 생각은...

1) &변수를 사용해서 참조하는데 시간이 오래걸린다. (하지만 아닌거 같아요...)

2) 위 소스는 -1인지 아닌지를 확인하는데, 아래소스는 0인지 아닌지를 확인하기 때문에 비교할때 차이가 많이 난다.

이거밖에 없는거 같은데 도대체 뭐가 시간초과를 일으킬까요??

아니라면 예외가 있어서 멈추지 않는걸까요??

// 아 그리고 아래 소스는 memset을 사용하지 않았는데, 사용해서 제출해도 결과에 큰 영향을 미치지 않았습니다. memset 때문은 아닌거 같습니다.

// 시간초과가 발생함
#include <cstdio>
#include <cstring>
int cache[2001][2001];
int arr[2001];
bool palin(int s,int e){
	if(s>e) return 1;
	int &ret=cache[s][e];
	if(ret!=-1) return ret;
	if(arr[s]!=arr[e]) return ret=0;
	return palin(s+1,e-1);
}
int main(){
	int N;
	scanf("%d",&N);
	memset(cache,-1,sizeof(cache));
	for(int i=1;i<=N;i++)
		scanf("%d",&arr[i]);
	int M;
	for(scanf("%d",&M);M--;){
		int S,E;
		scanf("%d%d",&S,&E);
		printf("%d\n",palin(S,E));
	}
	return 0;
}
// 시간초과가 나지 않음
#include<cstdio>
#include<cstring>
const int MAX_N = 2e3;
int n,m,a[MAX_N],pa[MAX_N][MAX_N],ck[MAX_N][MAX_N];
int f(int x, int y) {
    if (x > y) return 1;
    if(ck[x][y]) return pa[x][y];
    ck[x][y] = 1;
    return pa[x][y] = f(x + 1, y - 1)&(a[x] == a[y]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    scanf("%d", &m);
    for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), printf("%d\n", f(x-1, y-1));
    return 0;
}

h0ngjun7 7년 전 1

위의 코드 : ret 갱신을 안함.

밑의 코드 : 메모이제이션 잘 함.

#include <cstdio>
#include <cstring>
int cache[2001][2001];
int arr[2001];
bool palin(int s,int e){
    if(s>e) return 1;
    int &ret=cache[s][e];
    if(ret!=-1) return ret;
    if(arr[s]!=arr[e]) return ret=0;
    return ret = palin(s+1,e-1);
}
int main(){
    int N;
    scanf("%d",&N);
    memset(cache,-1,sizeof(cache));
    for(int i=1;i<=N;i++)
        scanf("%d",&arr[i]);
    int M;
    for(scanf("%d",&M);M--;){
        int S,E;
        scanf("%d%d",&S,&E);
        printf("%d\n",palin(S,E));
    }
    return 0;
}

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