TRIPATHCNT 문제 질문입니다

  • pumpyboom
    pumpyboom

    시간초과가 뜨네요...

    정말 오랫동안 시간 들여서 푼 문제거든요...
    정답을 기대헀는데 시간초과라는 결과가 뜨네요...

    시간초과를 줄이는 효율적인 방법ㅇ ㅣ뭐가있을까요?

    굳이 이문제 뿐만이 아니라... 방법론적으로...

    시간초과를 줄일려면 뭘 더 생각 해봐야 할까요?


    4년 전
4개의 댓글이 있습니다.
  • pumpyboom
    pumpyboom

    #define _CRT_SECURE_NO_WARNINGS
    #include
    #include

    int cnt = 0;
    int findMaxTree(int ** ar, int size, int i, int j, int n1, int n2);
    void findWay(int ** ar, int size, int i, int j, int n1, int n2, int max);

    int main(void)
    {

    int testCase;
    int n;
    int ** ar;
    int max = 0;
    
    scanf("%d", &testCase);
    
    
    for (int i = 0; i < testCase; i++)
    {
    
        scanf("%d", &n);
    
        ar = (int**)malloc(sizeof(int*)*n);
    
        for (int i = 0; i < n; i++)
            ar[i] = (int*)malloc(sizeof(int)*(i + 1));
    
    
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
                scanf("%d", &ar[i][j]);
        }
    
    
        max = findMaxTree(ar, n, 0, 0, ar[0][0], ar[0][0]);
    
        findWay(ar, n, 0, 0, ar[0][0],ar[0][0],max);
    
        printf("%d", cnt);
    
        cnt = 0;
    }
    
    return 0;

    }

    void findWay(int ** ar, int size, int i, int j, int n1,int n2, int max)
    {

    if (i >= size - 1)
    {
        if (n1 == max)
            cnt++;
    
        return;
    }
    
    
    int x1 = n1;
    int x2 = n2;
    
    x1 += ar[i+1][j];
    x2 += ar[i + 1][j + 1];
    
    findWay(ar, size, i + 1, j, x1, x1, max);
    findWay(ar, size, i + 1, j + 1, x2, x2, max);
    
    
    return;

    }

    int findMaxTree(int ** ar, int size, int i, int j, int n1, int n2)
    {

    int x1 = n1;
    int x2 = n2;
    
    if (i >= size - 1)
    {
        if (x1 > x2)
            return x1;
        else
            return x2;
    }
    
    x1 += ar[i + 1][j];
    x2 += ar[i + 1][j + 1];
    
    int len1 = findMaxTree(ar, size, i + 1, j, x1, x1);
    int len2 = findMaxTree(ar, size, i + 1, j + 1, x2, x2);
    
    if (len1 >= len2)
    {  
        return len1;
    }
    else
    {
        return len2;
    }

    }


    4년 전 link
  • pumpyboom
    pumpyboom

    이것은 제가 짠 코드이긴한데... 코드에 대한 문제보다는...
    시간초과를 해결하는 생각을 좀 더 듣고싶습니다


    4년 전 link
  • fleo0917
    fleo0917

    중복계산을 없에야 합니다. 예를들어 3층짜리 삼각형의 각 칸을 아래처럼 순서대로 번호를 메기고,
    0
    1 2
    3 4 5
    각 위치에서의 함수호출을 f(위치)로 나타내면 f(0)는 이렇게 전개될겁니다.
    f(0) -> f(1)+f(2) -> f(3)+f(4)+f(4)+f(5)
    보시면 아시겠지만 f(4)가 두 번 호출됩니다. 3층짜리 피라미드에서는 겨우 두 번이지만 20층만 되도 수만번의 중복 호출이 발생합니다. 이걸 한 번으로 줄일 수 있는 방법을 생각해보세요.
    내가 만든 함수는 위치 뿐만 아니라 다른 인자도 받고 있으니까 중복이 아닌데? 라고 생각하실 수도 있겠지만 그게 사실 꼭 그 자리에 있어야 하는 건 아닙니다. 다른 방법으로 나타내는 방법을 생각해보세요.
    이 문제는 TRIANGLEPATH문제의 확장판입니다. 이걸 먼저 풀어보는 게 도움이 될 겁니다.


    4년 전 link
  • pumpyboom
    pumpyboom

    감사합니다! 나중에 다시 댓글로 답변 하겠습니다


    4년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.