글 읽기 - c++ 메모리 초과입니다

pty3595 4년 전 0

아래와 같은 코드에서 메모리 오류가 납니다. 코드블락에서 돌려봤을 때 30000까진 잘 나오고 90000부터도 잘 안나오던데 그 이유가 궁금합니다.

#include <cstdio>
int dp[1000001];

void make(int a)
{
    dp[1]=0;

    int x=1000000;



    if(a%3==0)
    {
        if(dp[a/3]==-1) make(a/3);
        if(dp[a/3]<x) x=dp[a/3];
    }
    if(a%2==0)
    {
        if(dp[a/2]==-1) make(a/2);
        if(dp[a/2]<x) x=dp[a/2];
    }
    if(dp[a-1]==-1) make(a-1);
    if(dp[a-1]<x) x=dp[a-1];


    dp[a]=x+1;


}

int main(void)
{
    int n;
    for(int i=0;i<=1000000;i++) dp[i]=-1;

	scanf("%d", &n);
    make(n);
	printf("%d", dp[n]);
	return 0;
}

nahwasa 4년 전 1

메모리초과는 너무 재귀호출이 많이되서 그렇지 않나 싶네요. 1000000입력에 대해 make함수가 999999번 불리니까요?!

이 부분은 고수분이 제대로 설명해주실듯하고..

그 전에 일단 dp 점화식을 잘못세우신듯합니다.

https://www.acmicpc.net/board/view/19169

요 글이 참고가 될 듯 합니다.

pty3595 4년 전 0

감사합니다.

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

문제

문제

출처

ICPC

c++ 메모리 초과입니다

pty3595 4년 전 0

nahwasa 4년 전 1

pty3595 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말