글 읽기 - acm craft

prnuimeer 6년 전 0

메모제이션을 사용해서 구현 했는데 예제를 돌려보니 다 맞는데 제출을하면 시간초과가 뜹니다. 아래 어떤 코드를 수정 해야 할까요?

#include <stdio.h>
double route( int, int, double*, int(*)[ 2 ] );
double max( double*, int );
int main()
{
    int T, N, K, W, i, j; 
    double R;
    scanf( "%d", &T );
    for( i = 1; i <= T; i++ ) {
        scanf( "%d%d", &N, &K ); 
        double Name[ 1000 ] = { 0 };
        for( j = 0; j < N; j++ ) {
            scanf( "%lf", &Name[ j ] );
        }
        int Next[ 100000 ][ 2 ] = { 0 };
        for( j = 0; j < K; j++ ) {
            scanf( "%d%d", &Next[ j ][0], &Next[ j ][1] );
        } 
        scanf( "%d", &W );
        R = route( W, K, Name, Next );
        printf( "%lf\n", R );
    }
    return 0;
}
double route( int W, int K, double* Name, int( *Next )[ 2 ] )
{    
    int i, j = 0;
    double Connect[ 1000 ] = { 0 };
    double Memo[ 1000 ] = { 0 };
    for( i = 0; i < K; i++ ) {
        if( Next[ i ][ 1 ]  == W ) {
            Connect[ j ] = ( double )Next[ i ][ 0 ];
            j++;
        }
    } 
    if( j == 0 ) {
        Memo[ W - 1 ] = Name[ W - 1 ];
        return Name[ W - 1 ];
    }
    
    else {
        if( Memo[ W - 1 ] != 0 ) {
            return Memo[ W - 1 ];
        }
        else {
            for( i = 0; i < j; i++ ) {
                Connect[ i ] = Name[ W - 1 ] + route( Connect[ i ], K, Name, Next );
                
            }
            Memo[ W - 1 ] = max( Connect, j );
            return max( Connect, j );
        }
    }
}

double max( double* Connect, int j )
{
    double max, temp;
    int i;
    for( i = 0; i < j - 1; i++ ) {
        if( Connect[ i ] >= Connect[ i + 1 ] ) {
            temp = Connect[ i ];
            Connect[ i ] = Connect[ i + 1 ];
            Connect[ i + 1 ] = temp;
        }
    }
    return Connect[ j - 1 ];
}    

jwg8679 6년 전 0

메모이제이션을 쓰셧다는건 DP로 푸신거같은데 이 문제는 DP가 아니라 위상정렬 (Topological Sort)를 의도하고 만든 문제이기 때문에 시간초과가 뜨는 것 같습니다.

위상정렬 사용하시면 시간에 맞게 들어오실듯 합니다.

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

문제

문제

출처

ICPC

acm craft

prnuimeer 6년 전 0

jwg8679 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말