글 읽기 - 메모리 초과 해결 방법

dong925 2년 전 0

아직 포인터나 동적할당에 대해 사용이 미숙한 코린이 인데여

답은 잘 나오는 거 같은데 메모리 초과가 떠서 실패하네요 ㅠㅠ

메모리 초과같은 경우는 어떻게 해결 방향을 잡아야 하나요???

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

int main()
{   
    int N, R, Q, i, j, x, y, z, Row = 0, Col = 0, cnt = 0;
    
    scanf("%d %d %d", &N, &R, &Q);
    
    int **arr = (int**) calloc(N, sizeof(int*));
    
    for (i = 0; i < N; i++)
    {
        arr[i] = (int*) calloc(N, sizeof(int));
    }
    
    int *memo_Row = (int*) calloc(N, sizeof(int));
    int *memo_Col = (int*) calloc(N, sizeof(int));
    
    for (i = 0; i < N - 1; i++)
    {
        scanf("%d %d", &x, &y);
        arr[x - 1][y - 1] = 1;
        arr[y - 1][x - 1] = 1;
    }
    
    x = R - 1, i = 0;
    
    do 
    {
        for (i ; i < N; i++)
        {   
            if (arr[x][i] == 1)
            {   
                if (Row == N - 1)
                {
                    memo_Row[Row] = x, memo_Col[Col] = i;
                    arr[i][x] = 0;    
                    x = i, i = -1;
                }
                
                else
                {
                    memo_Row[Row++] = x, memo_Col[Col++] = i;
                    arr[i][x] = 0;    
                    x = i, i = -1;    
                }
            }
        }
        
        if (Row == 0)
        {
            memo_Row[Row] = 0, memo_Col[Col] = 0;
        }
        
        else
        {   
            memo_Row[Row--] = 0, memo_Col[Col--] = 0;
            x = memo_Row[Row], i = memo_Col[Col] + 1;
        }
    } while (memo_Row[Row] != 0);
 

    for (i = 0; i < Q; i++)
    {
        
        scanf("%d", &z);
        
        x = z - 1, j = 0, cnt = 0;
        
        do 
        {
            for (j ; j < N; j++)
            {   
                if (arr[x][j] == 1)
                {   
                    if (Row == N - 1)
                    {
                        memo_Row[Row] = x, memo_Col[Col] = j;
                        cnt++;
                        x = j, j = -1;
                    }
                
                    else
                    {
                        memo_Row[Row++] = x, memo_Col[Col++] = j;
                        cnt++; 
                        x = j, j = -1;
                    }
                }
            }
            
            if (Row == 0)
            {
                memo_Row[Row] = 0, memo_Col[Col] = 0;
            }
            
            else
            {   
                memo_Row[Row--] = 0, memo_Col[Col--] = 0;
                x = memo_Row[Row], j = memo_Col[Col] + 1;
            }
        } while (memo_Row[Row] != 0);
        
        printf("%d\n", cnt + 1);
    }


    for (i = 0; i < N; i++)
    {
        free(arr[i]);
    }
    
    free(arr), free(memo_Row), free(memo_Col);

    return 0;
}

zenith82114 2년 전 0

N이 최대 10만이니까 int N*N개짜리 메모리를 할당하면 GB 단위가 됩니다.

N개짜리 1차원 메모리만 써도 풀 수 있는 문제입니다.

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

문제

문제

출처

ICPC

메모리 초과 해결 방법

dong925 2년 전 0

zenith82114 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말