글 읽기 - c ) 예제는 올바르게 출력 되는데 메모리 초과가 뜹니다.

limd123 2년 전 0

원인을 찾으려고 계속 시도해봤지만 못찾았습니다. 도움주시면 감사하겠습니다.

#include <stdio.h>
#include <string.h>
//큐 구현
int front=-1,rear=-1;
int queue[100000000];

void push(int a){
	queue[++rear]=a;
}

void pop(){
	front++;
}

int empty(){
	if(front==rear) return 1;
	return 0;
}

int frontt(){
	return queue[front+1];
}
//명령 수행한 값 리턴하는 함수
int d(int a){
	if(2*a>9999) return (2*a)%10000; 
	return (2*a);
}

int s(int a){
	if(a-1<0) return 9999;
	return a-1;
}

int l(int a){
	return (a%1000)*10+a/1000;
}

int r(int a){
	return (a%10)*1000+a/10;
}

int from[10001];
char f[10001];  //무슨 명령을 사용했는지 저장 
int check[10001];

void print(int n, int m) {  //역추적해서 출력
    if (n == m) return;
    print(n, from[m]);
    printf("%c",f[m]);
}

int main (){
	int t;
	scanf("%d",&t);
	while(t--){
		int a,b;
		scanf("%d %d",&a,&b); 
		memset(check,0,sizeof(check));
		memset(f,0,sizeof(f));
		memset(from,0,sizeof(from));
		from[a]=-1;
		check[a]=1;
		push(a);
		while(!empty()){
			int k=frontt();
			pop();
			if(!check[d(k)]){
				check[d(k)]=1;
				push(d(k));
				from[d(k)]=k;
				f[d(k)]='D';
			}
			if(!check[s(k)]){
				check[s(k)]=1;
				push(s(k));
				from[s(k)]=k;
				f[s(k)]='S';
			}
			if(!check[l(k)]){
				check[l(k)]=1;
				push(l(k));
				from[l(k)]=k;
				f[l(k)]='L';
			} 
			if(!check[r(k)]){
				check[r(k)]=1;
				push(r(k));
				from[r(k)]=k;
				f[r(k)]='R';
			} 
		}
		
		print(a,b);
		printf("\n");
	}
	
	return 0;
}

bupjae 2년 전 1

queue 배열에 필요한 메모리는 4 * 100000000 = 약 381 MB 로, 주어진 메모리 제한을 초과합니다.

이 문제 푸는데 queue 가 저 정도로 클 필요는 없으니 조금만 줄이면 됩니다.

limd123 2년 전 0

근데 또 줄이면 OutOfBounds에러가 뜹니다ㅠㅠ

limd123 2년 전 0

void qset ( ){

rear=-1;

front=-1;

}

위와 같이 큐 초기화 함수를 만들어서 테스트 케이스 시작마다 초기화 해줬더니 해결됐습니다.

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

문제

문제

출처

ICPC

c ) 예제는 올바르게 출력 되는데 메모리 초과가 뜹니다.

limd123 2년 전 0

bupjae 2년 전 1

limd123 2년 전 0

limd123 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말