글 읽기 - top-down형식은 메모리 초과, 메모리공간 계산이 맞나요?

chemicat53 3년 전 0

문제가 되는 코드는 아랫줄에 적어 두었습니다.

백준을 띄엄띄엄 풀다 보니 아직 많이 부족합니다.

이 문제를 Top down 형식으로 재귀를 사용하여 풀었으나, 제출에서 메모리 초과 에러가 뜹니다.

반복문을 사용한 bottomup형식은 에러가 뜨질 않는데, 그 이유는 대강 추측은 가능하나, 제대로 된 설명을 듣고싶어 질문올립니다.

추측건대, 코드의 dp함수는 n이 1000000인 경우에,

dp 함수 호출을 많이 하게 되어 메모리 초과가 나는것같은데, 어느정도까지 함수 콜을 해야 메모리 에러가 나질 않는건지, 궁금합니다.

메모리 제한이 128MB라고 했는데,

1000001개의 int형 공간 + 함수 스택 공간 * int min1, min2를 위한 공간 > 128MB인건가요?

#include <stdio.h>

int		dparr[1000001] = {0,};

int		dp(int	n)
{
	int		min1;
	int		min2;

	min1 = min2 = (100001);
	if (dparr[n])
		return (dparr[n]);
	if (n % 2 == 0)
		min1 = dp(n / 2) + 1;
	if (n % 3 == 0)
		min2 = dp(n / 3) + 1;
	min1 = (min1 < min2) ? min1 : min2;
	min2 = dp(n - 1) + 1;
	min1 = (min1 < min2) ? min1 : min2;
	dparr[n] = min1;
	return (dparr[n]);
}

int		main()
{
	int		n;

	dparr[1] = 0;
	dparr[2] = 1;
	dparr[3] = 1;
	scanf("%d", &n);
	printf("%d", dp(n));
	return (0);
}

palilo 3년 전 0

dp(1)을 실행하면 모든 if문은 false니까 통과하고

18번 줄에서 dp(0)을 호출할겁니다

dp(0)은 13번 줄의 if문이 true므로 dp(0)을 호출할겁니다.

... 반복

sonjaewon 3년 전 0

재귀 종료조건이 잘모되었군요

chemicat53 3년 전 0

아...맞군요.

아직 한참 부족하네요..

답변 감사합니다.

같은 문제 다시 실수하지 않도록 해야겠어요

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

문제

문제

출처

ICPC

top-down형식은 메모리 초과, 메모리공간 계산이 맞나요?

chemicat53 3년 전 0

palilo 3년 전 0

sonjaewon 3년 전 0

chemicat53 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말