글 읽기 - 1005번 25%에서 런타임에러...

nuclear852 8년 전 0

문제를 풀 때 저는 역방향으로

i번째 노드에 대해 부모 노드가 뭔지 order[i] []에 넣어놨고요

이걸 스택처럼 쌓는 식으로 bumoamount[i]를 만들어서 i번째 노드의 부모가 몇 개인지 세놨어요

그리고 end지점을 역으로 start식으로 삼고

dfs형식으로 경로가 가장 긴 걸 찾아서 답을 넣는 식으로 했는데

25%에서 막히네요.... stack overflow 같기도 하고 만약 overflow라면 어떻게 처리해야할지 감이 안잡혀서 질문 올립니다..

#include <iostream>
#include <stdio.h>
#include <stack>
using namespace std;
int main(void)
{
        int T;
        cin>>T;
        while(T--)
        {
                int N, K;
                cin>>N>>K;
                int value[N+1]; //time
                int order[N+1][N+1]; //reverse order
                int bumoamount[N+1]; //amount of parent in Node [i]
                int ans=0;

                for(int i=0; i<=N; i++)
                        bumoamount[i] = 0;

                for(int i=1; i<=N; i++)
                        scanf("%d",&value[i]);

                for(int i=0; i<K; i++){
                        int tmpa, tmpb;
                        scanf("%d%d",&tmpa,&tmpb);
                        order[tmpb][bumoamount[tmpb]] = tmpa;
                        bumoamount[tmpb]++;
                }

                stack<int> point;
                stack<long long> score;

                int start;
                cin>>start;

                point.push(start);
                score.push( value[start]);

                while( !point.empty())
                {
                        int pt = point.top();
                        long long sc = score.top();
                        point.pop();
                        score.pop();

                        if( bumoamount[pt] == 0)
                        {
                                if( sc > ans)
                                        ans = sc;
                        }

                        else
                        {
                                for(int i=0; i<bumoamount[pt]; i++)
                                {
                                        point.push( order[pt][i]);
                                        score.push( value[ order[pt][i] ] + sc);
                                }
                        }
                }
                cout<<ans<<endl;
        }
}

pl0892029 8년 전 0

컴파일 타임과 런 타임에 대해서 찾아서 살펴보세요. :)

cin>>N>>K;
int value[N+1]; //time

다른 오류가 더 있을수도 있습니다. 하지만 이게 먼저 눈에 띄는군요. 이 부분을 고치고 테스트해보시길 바랍니다.

nuclear852 8년 전 0

요거는 상관이 없는거 같던데.... 이게 N이 커질수록 에러를 발생하나요??

pl0892029 8년 전 0

@nuclear852 @baekjoon
자동으로 할당되는 것을 확인하고 강한 호기심에 조사를 해보았고, 공유드립니다.

"C99 표준에서만" 위 형태(동적인 변수를 배열의 할당 크기로 사용하는 형태)의 사용이 가능합니다.
그럼에도 불구하고 gcc, g++ 컴파일러에서는 (C, C++, C++11, C++14) 위 표준의 내용을 확장으로 지원하고 있기 때문에 사용될 수 있습니다.
(ref : http://www.geeksforgeeks.org/variable-length-array...)

C99 표준과 C++11, C++14 표준은 명확히 다르기 때문에, 정확하게 사용하기 위해서는 다음과 같은 옵션을 추가하여 확장 지원을 막을 수 있습니다.
ex) C++11 컴파일 옵션
g++ Main.cc -o Main -O2 -Wall -lm --static -pedantic -std=c++11 -DONLINE_JUDGE
(ref : http://stackoverflow.com/questions/17899274/g-vari...)

간단 요약 : GCC가 표준 내용을 확장 지원하기 때문에 돌아가게 되는 것이었다. (C++ 외에서는 컴파일 에러가 나는게 원칙상은 맞다.)

pl0892029 8년 전 0

@nuclear852

동적인 크기로 배열을 선언하게 되면, "함수 스택 메모리 공간"에 할당되게 됩니다.
그와 동시에, 큰 메모리 공간을 할당하는 경우에 스택 오버플로우 문제가 발생하게 됩니다.
(함수 스택 공간은 관리되는 메모리의 일부이기 때문에, 크기가 제한되어 있습니다.)

따라서 동적 크기의 배열이 필요한 경우 동적 메모리 할당을 통해서 관리하는 것이 좋습니다. ( STL의 vector, stack, queue와 같은)

위의 소스에서는 다음과 같은 부분이 함수 스택 메모리 공간을 매우 크게 차지하고 있으며, 스택의 크기가 작게 할당되는 환경에서는 프로그램이 비정상 종료될 수 있는 원인이 됩니다.

    int order[N+1][N+1]; //reverse order

pl0892029 8년 전 1

다시 원점으로 돌아와서 (-_-...) 위 문제에서 시간초과가 발생하는 이유는 스택을 쓰기 때문입니다.
특정 정점 X가 중복해서 방문이 되고, 거기서 많은 경우가 반복되는 경우 시간 초과에 걸릴 수 있습니다.
(정점 1은 정점 2,3에 연결되고, 정점 2,3은 정점 4에 연결되고, 정점 4는 정점 5,6에 연결되고, 정점 5,6은 정점 7에 연결되고.... 의 경우)

"X에 도달할 수 있다" 는 것은 "X의 선행 조건들이 모두 충족되었다." 라는 상황을 곰곰히 생각해보시면, X의 선행 조건이 충족되었을 때에만 X를 고려하면 됩니다. 이런 알고리즘이 위상정렬이죠.

위상정렬을 찾아보시고 다시 문제를 고민해보시는 것을 추천드립니다.

nuclear852 8년 전 0

감사합니당! 헤헤

더 배워 올게요

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

문제

문제

출처

ICPC

1005번 25%에서 런타임에러...

nuclear852 8년 전 0

pl0892029 8년 전 0

nuclear852 8년 전 0

nuclear852 8년 전 1

pl0892029 8년 전 0

pl0892029 8년 전 0

pl0892029 8년 전 1

nuclear852 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말