글 읽기 - 1005번 ACM-Craft 런타임에러나네요..

gusals224 7년 전 0

알고리즘은 다음과같습니다.

1부터 N까지 건물순서 중에 거꾸로 봤을때 두갈래인거

예를들어

1 3

2 3

인경우

과같이 3을 만들기 위한 경우가 두갈래 이상인경우만 따로 배열에 저장해두고

3 1

3 2

과같이 거꾸로 배열을 채운뒤 시간을 모두 합해보고 가장 많이걸리는 시간이

최종 걸리는시간으로 풀었는데요... 런타임에러가 자꾸 나오네요;;

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main()
{
    int t,i,qq;
    int n,k;
    
    scanf("%d",&t);
    
    for(;t>0;t--)
    {
        scanf("%d%d",&n,&k);
        int *tim=new int[n+1];
        int **order;
  order=new int*[k];
  for(qq=0;qq<k;qq++)
  {
   order[qq]=new int[2];
  }
  
  
    
        for(i=0;i<n;i++)
        {
            scanf("%d",&tim[i+1]);
        }
        for(i=0;i<k;i++)
        {
            scanf("%d%d",&order[i][0],&order[i][1]);
        }
  //tim 건물짓는시간
  //order 건물짓는순서
        //모든값 받기

        int *count=new int[n+1];
        int j=0;
        int **multi;
  multi=new int *[n+1];
  for(qq=0;qq<n+1;qq++)
  {
   multi[qq]=new int[k];
  }
        
        memset(count,0,n*4);
        for(i=0;i<n+1;i++)
            memset(multi[i],0,n*4);
        
        for(i=0;i<k;i++)//두갈래가 몇개인지 확인
        {
            count[order[i][1]-1]++;
        }
    
        for(i=0;i<n;i++)//2갈래에서 바로 전에 지을 수있는경우들 예를들어 7 5, 7 4 같이;;
        {
            if(count[i]>2)
            {
                multi[j][0]=i+1;
                count[i]--;
                j++;
            }
            else if(count[i]==2)
            {
                multi[j][0]=i+1;
                j++;
                multi[j][0]=i+1;
                j++;
                count[i]-=2;
            }
        }
        
        int num;//모든 경우 예를들어 7 5 3 1, 7 4 2 1 같이
        for(i=0;i<j;i++)
        {
            num=1;
            for(int m=0;m<k;m++)
            {
                if(order[m][1]==multi[i][0])
                {
                    multi[i][1]=order[m][0];
                    order[m][0]=0;
                    order[m][1]=0;
                    break;
                }
            }
            
            for(int h=0;h<n;h++)
            {
                if(order[h][1]==multi[i][num])
    {
                    multi[i][num+1]=order[h][0];
                    h=-1;
                    num++;
                }
            }
        }
        
        
        
        int max=0;	//각각의 경우에 시작점이 같으면 max시간을 계산해보고 가장 큰것이 걸리는 시간으로 판단
        int smax=0;
        int rem=multi[0][0];
        for(i=0;i<j+1;i++)
        {
            if(rem==multi[i][0])
            {
                
            }
            else
            {
                rem=multi[i][0];
                if(tim[multi[i-1][0]]<max)
                    tim[multi[i-1][0]]=max;
                max=0;
                smax=0;
            }    
            for(int m=0;1;m++)
            {
                if(multi[i][m]==0)
                    break;
                smax+=tim[multi[i][m]];
            }
            if(smax>max)
                max=smax;
            smax=0;
        }
        
        int *fin=new int[n+1];
        memset(fin,0,sizeof(fin)*4);
        int nu=0;
        int fina;
        scanf("%d",&fina);	//마지막 값 입력받기
        fin[0]=fina;
        
        
        for(i=0;i<k;i++)
        {
            if(fin[nu]==order[i][1])
            {
                fin[++nu]=order[i][0];
            }
        }
        
        max=0;
        for(i=0;1;i++)
        {
            if(fin[i]<=0)
            break;
            else
            {
              max=max+tim[fin[i]];  
            }
        }

        printf("%d\n",max);	//걸리는 시간 출력
    }
    
    
    return 0;    
}

	

Nada 7년 전 0

multi 배열이 multi[1001][100001] 의 크기를 잡으셨는데 이 경우에

heap 메모리 초과여서 런타임 에러가 발생합니다.

또한 전역변수로 배열을 잡으셔도 메모리 초과가 발생하겠네요.

또한 memset(count,0,n*4); for(i=0;i<n+1;i++) memset(multi[i],0,n*4);

이 파트에서 multi[i]의 크기는 (k+1)*4인데 n*4로 하셨네요. 다시 말해 n < k 경우

런타임 에러가 발생합니다.

추가적으로 memset(fin,0,sizeof(fin)*4); 이 아니라 memset( fin, 0, sizeof(fin) );

으로 하셔야 하고 이 역시 런타임 에러의 원인 같네요.

gusals224 7년 전 0

감사합니다. .ㅎㅎㅎ 배열 크기가 문제가 되는군요..코드를 다시 짜봐야 겠네요 ㅎㅎ

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

문제

문제

출처

ICPC

1005번 ACM-Craft 런타임에러나네요..

gusals224 7년 전 0

Nada 7년 전 0

gusals224 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말