글 읽기 - 이차원 배열 선언만 해도 터져요..

kysloves 6년 전 2

[알고리즘 설명]

다이나믹 프로그래밍으로 풀었습니다. 그런데 37행의 int adjMat[1001][1001] 때문에 계속 프로그램 오류창이 뜹니다. 동적할당으로 방법을 바꿔서 했더니 제대로 실행되고 예제도 다 맞게 나왔지만 백준에선 런타임 에러에 걸려버렸구요. 혹시나해서 아래코드도 제출해보니 역시 런타임에러라고 뜨네요 ..

[궁금한 것]

저 adjMat[1001][1001]의 선언에서 계속 오류가 나는 것 같아요. (다른 소스코드에서 시도해봤는데 [501][501] 크기까진 커버가 돼도 [1001][1001]로 범위가 커지니까 바로 프로그램 오류가 나더라구요.)

저렇게 커다란 2차원 배열은 어떻게 코드를 짜줘야할까요?

고수님들의 의견을 구합니다 ㅠㅠ

#include <stdio.h>
#include <stdlib.h>


int DFS(int target,int N, int time[],int DP[],int adjMat[][1001]){
	int max=0,result=0;
	int i,answer;


	if(DP[target]!=0){
		return DP[target];
	}

	for(i=1;i<=N;i++){
		if(adjMat[i][target]==1){
			result=DFS(i,N,time,DP,adjMat);
			if(max<result){
				max=result;
			}
		}
	}

	answer=time[target]+max;
	if(DP[target]<answer){
		DP[target]=answer;
	}
	return answer; 
}

int main(){

	
	int T,N,K,i,j,x,y,w;
	int testCase[1001]={0};
	int time[1001]={0};
	int DP[1001]={0};
	int adjMat[1001][1001];// 문제의 코드!!!!!!!!!!!!!!!!!!!!!!!!
	
	scanf("%d",&T);
	
	for(i=0;i<T;i++){
		scanf("%d%d",&N,&K);
		
		for(j=0;j<=N;j++){ //DP 초기화
			DP[j]=0;
		}
		

		for(j=1;j<=N;j++){
			scanf("%d",&time[j]);
		}

		for(j=0;j<K;j++){
			scanf("%d%d",&x,&y);
			adjMat[x][y]=1;
		}

		scanf("%d",&w);

		testCase[i]=DFS(w,N,time,DP,adjMat);
		
	}

	for(i=0;i<T;i++){
		printf("%d\n",testCase[i]);
	}

	return 0;
}

hj_d 6년 전 1

전역변수로 써보세요

portableangel 6년 전 1

전역으로 빼세요.

근데 전역으로 빼면.. 시간초과네요.

kysloves 6년 전 0

hj_d 님, portableangel님 정말 감사합니다!

전역변수로 빼고 그에 맞춰 코드를 조금 수정했더니 통과하였습니다.

이미 해결된 질문이긴 하지만 왜 전역변수일때는 오류가 나지 않는 것인가요? 수업시간에 배운 전역변수와 지역변수의 차이점은 해당 변수의 영향력 "범위"라고만 배웠는데, 할당가능한 사이즈에도 차이가 있는건가요?

simm4256 6년 전 6

전역변수 쓰신거 다시 지역으로 넣어도 맞을겁니다.

아마 VS를 쓰시는것 같은데 간단히 말씀드리면

지역 변수는 힙 메모리를 사용하고 전역 변수는 스택 메모리를 사용합니다.

근데 힙 메모리의 제한이 VS에선 굉장히 적습니다.

해결법은 애초에 전역변수로 코딩하시거나

VS 메뉴에서

프로젝트 - [파일명] 속성 - 좌측메뉴에 링커 - 시스템

가셔서 '힙 예약 크기' 부분을 바꿔주시면 됩니다.

일반적인 문제의 메모리제한이 256MB정도니

1024*1024*256 = 268435456

이라고 넣고 돌리시면 지역 변수에서도 큰 배열의 선언이 가능합니다.

참고로 이는 VS 기본 설정의 문제고, 백준 저지 시스템은 VS로 돌아가는 게 아니라서 그냥 지역에다가 큰 배열 잡고 제출해도 통과됩니다.

kysloves 6년 전 0

simm4256 님 친절한 설명 정말 감사합니다! 오늘도 배워가네요, 좋은 하루 되세요!

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

문제

문제

출처

ICPC

이차원 배열 선언만 해도 터져요..

kysloves 6년 전 2

hj_d 6년 전 1

portableangel 6년 전 1

kysloves 6년 전 0

simm4256 6년 전 6

kysloves 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말