글 읽기 - 99%에서 메모리 초과가 뜹니다..

masioka 6년 전 0

피보나치 행렬 곱 방식으로 풀었습니다. 재귀호출을 사용했구요.

재귀호출로는 100경까지라 해도 n/2로 떨어지는 줄어들기때문에 스택오버플로우도 안난다고 계산했습니다.

100경까지 입력해도 답이 잘 뜨더군요. 그래서 제출했는데 99%에서 메모리 초과가 뜨네요..

제가 이전에 시도한 소스코드는 이차원 배열 반환 함수를 사용했습니다. 그래서 필수적으로 함수 안에서 static으로 2차원 배열 선언을 했구요.

static 변수때문에 메모리 초과가 나는건가 싶어서 아래의 소스코드 처럼 바꿨습니다.

전역변수로 배열 3개 만들어서 해결했는데도 똑같이 99%에서 메모리 초과과 나네요..

이유를 모르겠습니다. 도와주세요 ㅜ.ㅜ

#include <stdio.h>
long long f[2][2] = { 1,1,1,0 };
long long a[2][2], b[2][2], c[2][2];
void mul(long long x[][2], long long y[][2]) {
	a[0][0] = x[0][0], a[0][1] = x[0][1];
	a[1][0] = x[1][0], a[1][1] = x[1][1];
	b[0][0] = y[0][0], b[0][1] = y[0][1];
	b[1][0] = y[1][0], b[1][1] = y[1][1];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % 1000000;
		}
	}
}
void fibo(unsigned long long x) {
	if (x == 1) {
		c[0][0] = 1, c[0][1] = 1;
		c[1][0] = 1, c[1][1] = 0;
		return;
	}
	if (x % 2 == 0) {
		fibo(x / 2);
		mul(c, c);
	}
	else {
		fibo(x / 2);
		mul(c, c);
		mul(c, f);
	}
}
int main() {
	unsigned long long n;
	scanf("%llu", &n);
	fibo(n - 1);
	printf("%lld", c[0][0]);
}

jh05013 6년 전 0

1을 넣으면 안 돌아갑니다.

djm03178 6년 전 0

편법이지만 보통 테스트 케이스가 많은 문제에서 매우 높은 %에서 문제가 생기면 상한, 하한의 입력들을 처리하지 못하는 것일 가능성이 높습니다.

masioka 6년 전 0

아.. n=1일때가 스택오버플로우가 뜨네요..

1의 경우를 처리하는 것을 깜빡했었네요.. 감사합니다

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

문제

문제

출처

ICPC

99%에서 메모리 초과가 뜹니다..

masioka 6년 전 0

jh05013 6년 전 0

djm03178 6년 전 0

masioka 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말