글 읽기 - 메모리초과 질문입니다...

lg970325 7년 전 0

메모리 초과 어떻게 해결하나요??????

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

int min2(int a,int b)
{
    if(a<b)
        return a;
    else
        return b;
}

int max2(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}

int min3(int a,int b,int c)
{
    int m;
    if(a<b)
        m=a;
    else
        m=b;
    if(m<c)
        return m;
    else
        return c;
}

int max3(int a,int b,int c)
{
    int m;
    if(a>b)
        m=a;
    else
        m=b;
    if(c>m)
        return c;
    else
        return m;
}

int main(void)
{
    int n,i,j;
    scanf("%d",&n);
    int **map=(int**)malloc(sizeof(int*)*n);
    for(i=0;i<n;i++)
        map[i]=(int*)malloc(sizeof(int)*3);
    
    int* max=(int*)malloc(sizeof(int)*n);
    int* min=(int*)malloc(sizeof(int)*n);
    
    int** d=(int**)malloc(sizeof(int*)*n);
    for(i=0;i<n;i++)
        d[i]=(int*)malloc(sizeof(int)*3);
    
    for(i=0;i<n;i++)
    {
        for(j=0;j<3;j++)
            scanf("%d",&map[i][j]);
    }
    
    d[0][0]=map[0][0];
    d[0][1]=map[0][1];
    d[0][2]=map[0][2];
    min[0]=min3(d[0][0],d[0][1],d[0][2]);
    for(i=1;i<n;i++)
    {
        d[i][0]=map[i][0]+min2(d[i-1][0],d[i-1][1]);
        d[i][1]=map[i][1]+min3(d[i-1][0],d[i-1][1],d[i-1][2]);
        d[i][2]=map[i][2]+min2(d[i-1][1],d[i-1][2]);
        min[i]=min3(d[i][0],d[i][1],d[i][2]);
    }
    
    
    d[0][0]=map[0][0];
    d[0][1]=map[0][1];
    d[0][2]=map[0][2];
    max[0]=max3(d[0][0],d[0][1],d[0][2]);
    for(i=1;i<n;i++)
    {
        d[i][0]=map[i][0]+max2(d[i-1][0],d[i-1][1]);
        d[i][1]=map[i][1]+max3(d[i-1][0],d[i-1][1],d[i-1][2]);
        d[i][2]=map[i][2]+max2(d[i-1][1],d[i-1][2]);
        max[i]=max3(d[i][0],d[i][1],d[i][2]);
    }
    
    printf("%d %d",max[n-1],min[n-1]);
    
    free(max);
    free(min);
    
    for(i=0;i<n;i++)
        free(d[i]);
    free(d);
    
    for(i=0;i<n;i++)
        free(map[i]);
    free(map);
    
    return 0;
}

yclock 7년 전 3

배열을 잡을 때 O(N)만큼 잡을 필요가 없습니다...!

배열 d에서 원소 d[k][0-2]의 값을 구하기 위해서는 오직 d[k-1][0-2]와 map[k][0-2]부분만 필요하기 때문에

배열을 참조하는 부분만 잡아서 "메모리 초과"를 해결할 수 있습니다!!!

yclock 7년 전 3

예를 들어서 N번째 피보나치 수를 구하려고 할 때, 다음과 같이 문제를 해결할 수 있습니다.

같은 아이디어를 사용했으므로 참고해주시면 감사하겠습니다.

    // 방법 1 : O(N)의 배열을 모두 잡는다.
    {
        int fibo[N] = {1, 1};
        for(int i = 2; i < N; fibo[i] = fibo[i-1] + fibo[i-2], i++);
        printf("%d\n", fibo[N-1]);
    }

    // 방법 2 : 필요한 부분만 잡는다.
    {
        // 피보나치 수열에서 k번째 수를 구하기 위해서는 (k-1)번째 수와 (k-2)번째 수만 필요하므로,
        // 배열의 크기가 3만 되어도 충분하다.
        int fibo[3] = {1, 1};
        
        // 다음 for문 내부에서 배열 fibo에 저장되어 있는 값은 다음과 같을 것이다.
        // fibo[2] = (i+1)번째 수, fibo[1] = i번째 수, fibo[0] = (i-1)번째 수.
        for(int i = 2; i < N; i++) {
            fibo[2] = fibo[1] + fibo[0]; // (i+1)번째 수를 그 전의 2개의 값을 참고하여 구한다.
            fibo[0] = fibo[1]; fibo[1] = fibo[2]; // fibo 배열의 원소를 앞으로 하나씩 민다(!!!) <- 이 아이디어의 핵심
        }
        
        // 위의 for문 내부에서 마지막에 fibo 배열의 원소를 앞으로 하나씩 밀었으므로, 현재 fibo[1]에는 N번째 수가 들어가 있게 된다.
        // 출력 시 주의한다.
        printf("%d\n", fibo[1]);
        // 이 때 printf("%d\n", fibo[2]);를 해도 똑같은 값이 들어가 있기 때문에 상관은 없습니다...
    }

    // 이러한 기법을 뭐라고 했는데 기억이 안나요;; 죄송합니다.

lg970325 7년 전 1

아~

친절한 답변 감사합니다!!!

yclock 7년 전 3

여담입니다만,

저도 지금 알았는데

이 문제를 100000*3크기 배열 2개 잡고 편하게 돌려도 AC가 나오네요...

lg970325 7년 전 1

성공했어요!

감사합니다~~

wjddms206 7년 전 1

yclock 님 덕에 저도 잘 풀었어요. 정말 감사해요!!!

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

문제

문제

출처

ICPC

메모리초과 질문입니다...

lg970325 7년 전 0

yclock 7년 전 3

yclock 7년 전 3

lg970325 7년 전 1

yclock 7년 전 3

lg970325 7년 전 1

wjddms206 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말