글 읽기 - 5%에서 시간초과가 나는 이유가 뭘까요?ㅠㅠ

ccaa38 7년 전 0

소스 첨부하였습니다. ㅠㅠ

5퍼센트에서 시간초과가 나는데

어 떤 테스트케이스를 놓친건지 알고 싶습니다.

어떤걸 넣어봐야할까요ㅠㅠ ㅎ ㅏ..이거때문에 잠도 안오네요

int N, M,K; // M 개 이하의 도시
vector< vector< pair<int,int> > > map;

vector< int > visit;

int kk=0;

int search(int x,int count)

{

    if(x == N) return 0;

    if(x != N && count == 0) return -987654321;

    ///if(count<0) return -123456789;

    //if(check[x] == 1) return visit[x]; // 방문했다는 뜻

    for(int i =0;i< map[x].size(); i++ )

    {

        int next = map[x][i].first;

        int next_bab = map[x][i].second;

        if(next > x) //큰 숫자로만 간다.

        {

            visit[x] = max(search(next,count-1) + next_bab, visit[x]);

       //     check[x] = 1;

        }

    }

    return visit[x];

}

int main()

{

    scanf("%d %d %d", &N, &M,&K);

    map.resize(N+1);

    visit.resize(N+1);

    for (int i = 1; i <= K; i++)

    {

        int a,b,c;

        scanf("%d %d %d",&a,&b,&c);

        map[a].push_back(make_pair(b,c));

    }

    printf("%d\n", search(1,M-1));

    return 0;

}

​

zlzmsrhak 7년 전 0

N = M = 300, K = 100000짜리를 랜덤으로 데이터를 만들면 시간초과가 나올 것 같습니다.

메모이제이션을 이용한 DP를 의도하신 것 같으니까 그쪽으로 설명하면,

함수 인자가 2개니까 visit 배열을 2차원 배열로 정의해야 하고, 주석처리 되어 있는 것들을 잘 수정하면 될 것 같습니다.

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

문제

문제

출처

ICPC

5%에서 시간초과가 나는 이유가 뭘까요?ㅠㅠ

ccaa38 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말