글 읽기 - 제 컴퓨터에서는 실행이 안되는데 이 코드가 왜 AC가 되나요?

xowns9418 6년 전 0

문제의 n 최대값은 10000입니다. 그런데, 제 코드로는 약 5000번째 피보나치수 까지는 잘 출력이 되는데 6000정도 되면 실행이 안되고 종료됩니다. 혹시나 해서 제출해봤더니 AC가 뜨네요.... 왜 일까요?

아래는 제 코드입니다.

코드에 대해 간단히 설명 드리면 피보나치수의 자리수가 커질거 같아서 dp배열을 string으로 만들고 피보나치 값을 저장했습니다.

//피보나치 수 4 10826번
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MAX_SIZE 10001

string dp[MAX_SIZE];

string calc(string s, string s2) {

	string ret;
	int len, len2;
	int a, b, carry_before, carry_now;

	len = s.length();
	len2 = s2.length();

	carry_before = carry_now = 0;

	if (len < len2) {

		for (int i = 0; i < len2 - len; i++) {

			s.insert(s.begin(), '0');
		}

		len = len2;
	}

	else if (len2 < len) {

		for (int i = 0; i < len - len2; i++) {

			s2.insert(s2.begin(), '0');
		}
	}

	//문자의 길이를 맞춘후 계산(두 문자중 긴 문자의 길이 까지 돌림)
	for (int i = len - 1; 0 <= i; i--) {

		a = s[i] - '0';
		b = s2[i] - '0';

		carry_before = carry_now;

		if (a + b + carry_before < 10) {

			carry_now = 0;
			ret += (a + b + carry_before) + '0';
		}

		else {

			carry_now = 1;
			ret += (a + b + carry_before - 10) + '0';

			if (i == 0 && carry_now == 1) ret += '1';
		}
	}

	reverse(ret.begin(), ret.end());

	return ret;
}

string fibo(int n) {

	if (dp[n] != "-1") return dp[n];

	if (n == 0) {

		dp[n] = "0";
		return dp[n];
	}

	else if (n == 1) {

		dp[n] = "1";
		return dp[n];
	}

	return dp[n] = calc(fibo(n - 1), fibo(n - 2));
}

int main(void) {

	int n;

	cin >> n;
	for (int i = 0; i <= n; i++) dp[i] = "-1";

	fibo(n);

	cout << dp[n];

	return 0;
}

sgchoi5 6년 전 0

Win 10 + 64 bit + 8 GB 램 + Visual Studio Community 2017 에서는 10000 까지 잘 되는데요..

PC 환경이 어떻게 되세요?

xowns9418 6년 전 0

Win 10 , 64bit , 8GB 램, Visual 2015 쓰고 있습니다. n에 10000을 입력하면 그림과 같이 값이 출력이 안되면서 실행창이 닫깁니다..

저도 vs2015에서 해보니 프로그램이 죽는데, 스택 오버플로우 때문입니다. 재귀 함수 호출이 너무 깊어서 중간에 기본 할당 스택 크기를 넘어가버리는 것 같아요. 2017에서는 기본 스택 사이즈가 좀 더 큰가 싶기도 하네요. 그리고 debug로 하면 6000쯤에서 죽는데 release로 해보시면 9900 언저리까지 돌아갑니다. 스택 아슬아슬하게 넘는 거 같아요. 여기 채점 환경이 vs보다 기본 스택 사이즈가 더 커서 통과되는지 아니면 뭐 gcc쪽에서는 재귀 함수 호출에서 스택 메모리를 좀 덜 먹는지는 모르겠지만 아무튼 아슬아슬하게 통과가 되나 보네요.

vs에서도 프로젝트 속성 - 링커 - 시스템 - 스택 예약 사이즈 를 넉넉하게 수정하시면 안 죽고 돌아갑니다.

xowns9418 6년 전 0

@jwvg0425 아 그렇군요...속성을 바꿔봐야겟네요 !! 감사합니다 !!!

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

문제

문제

출처

ICPC

제 컴퓨터에서는 실행이 안되는데 이 코드가 왜 AC가 되나요?

xowns9418 6년 전 0

sgchoi5 6년 전 0

xowns9418 6년 전 0

jwvg0425 6년 전 3

xowns9418 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말